HashTable은 Key - Value 쌍으로 데이터를 저장하는 자료구조이다.

HashMap으로 불리기도 하며 python의 dictionary는 HashTable로 구현되어 있으며 다음과 같은 내부 구조를 가진다.

keys → buckets 부분을 좀 더 자세히 표현하면 다음과 같다.

dictionary는 여러개의 bucket으로 이루어져 있다.

• bucket : hash table은 각각의 key값에 hash function 적용해 배열의 고유한 index를 생성하고 이 index를 활용해 값을 저장 / 검색하는데, 이 실제 값이 저장되는 장소(배열)이 bucket이다.
• 만약 (”윤채영”, “1234-5678”)인 데이터를 hash table에 저장하려면 다음과 같은 절차가 수행된다.
  • 특정 hash function으로 index 연산
    • index = hash_func(”윤채영”)
  • 해당 index로 value 조회
    • bucket[index] = “1234-5678”

이러한 구조는 key값으로 데이터를 찾기 위해 hash function 한번만 수행하면 되기 때문에 데이터 저장/삭제/조회가 매우 빠르다 → 평균 시간복잡도 $O(1)$

• 참고로 python dictionary 는 처음에 생성하면 8 empty buckets로 시작하는데, 용량이 찰때바마다 2배로 사이즈가 증가한다.
• dictionary.clear() method는 initial default space까지 정리해준다.