해쉬 테이블

 

Key-Value 구조로 데이터를 저장하는 자료구조로, 배열보다 검색과 삽입에 더 빠른 효율을 보인다.

C++을 사용할 때 흔히 사용하는 map 자료구조를 구현할 때 가장 효율적으로 사용되는 방법이다.

 

Hash란 무엇일까?

해쉬 테이블은 내부에 array와 같은 구조가 있지만, hash function 덕분에 선형 검색을 하지 않고 빠르게 값을 찾을 수 있다.

해쉬 함수는 우리가 입력하는 key 값을 어떠한 정수값으로 치환하여 array의 index로 변환한다.

이 때, 각각 다른 key에 대해 해시함수가 동일한 index를 부여하는 경우 해쉬 충돌(hash collision)이라고 한다.
이 해쉬 충돌의 대표적인 대처 방법은 다음과 같다.
index가 가리키는 저장소 안에 또 다른 배열을 생성하여 같은 index를 공유하는 key들을 그 안에 집어 넣는 방법이다.
이 때 이 key들을 검색하라는 명령이 들어올 경우, 해쉬 함수가 치환한 해당 index 안에서 특정 값을 찾기 위해 내부의 또 다른 배열에 대한 선형 검색을 하게 된다. 즉 이런 경우에는 O(1)이 아니라 O(N)이 되는 것이다.