▪️  key & value : 사전을 구현하는 효율적인 자료구조

▪️  hash function(key) → bucket

해시테이블에서의 시간 복잡도

<aside> ⏰ 삽입/삭제/ 탐색: O(1) ** 단 최악의 경우 O(n) 이 될 수 있음*

</aside>

※ 삽입/삭제 시간 복잡도가 O(1) 인 이유

: 각 버킷의 원소는 linked-list 형태 → 앞 뒤 노드의 참조 관계만 수정

※ 탐색의 시간 복잡도가 O(1) 인 이유

: 키는 고유하기 때문에 이를 해싱한 값을 인덱스로 사용할 수 있기 때문

※ 최악의 경우 시간 복잡도가 O(n) 인 이유

: Collision