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 한번만 수행하면 되기 때문에 데이터 저장/삭제/조회가 매우 빠르다 → 평균 시간복잡도
•
참고로 python dictionary 는 처음에 생성하면 8 empty buckets로 시작하는데, 용량이 찰때바마다 2배로 사이즈가 증가한다.
•
dictionary.clear() method는 initial default space까지 정리해준다.
