해시 테이블(Hash Table)

해시 테이블(Hash Table)

해시 테이블은 Key - Value 값으로 데이터를 저장하는 자료구조이다. 해시 테이블은 빠른 검색속도를 자랑한다.
해시 테이블이 빠른 검색속도를 제공하는 이유는 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 여기서 실제 값이 저장되는 자소를 버킷 또는 슬롯이라고 한다.

index = hash_function(key) % 16
array[index] = value

이러한 해싱 구조로 데이터를 저장하면 key 값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다.

데이터의 충돌이 발생한 경우

각각 다른 key값을 해시 함수를 돌려 나온 값이 동일할 수 있다. 이럴 경우에 데이터의 충돌이 생기는데 이는 분리 연결법과 개방 주소법 크게 2가지로 해결한다고 한다. 자세한 내용은 다루지 않는다.

하여튼, 데이터의 충돌이 발생한 경우 버킷에 Chaning을 하여 연결된 리스트들까지 검색을 해야하므로, O(N)까지 시간복잡도가 증가할 수 있다고 한다.