hash table

hash table은 배열을 바탕으로 한 자료구조다.

삽입 및 검색을 할 때 매우 빠른 속도로 처리한다. 

그러나 배열을 기반으로 했기 때문에, 크기가 제한되어 있다.

 

hash function을 사용하여, 각 key들에 index를 부여한다. 이러한 index가 있기에, 각 key에 빨리 접근하여 value를 가져올 수 있다.

 

그러나 index 번호가 겹칠 경우 충돌이 일어날 수 있다. 이러한 충돌을 방지하기  위한 방법 중 유명한 방법은 chaining과 linear probing이다.

Chaining은 linkedlist와 결합하여 사용하는 방식으로, 다른 value를 가진 key 가 동일한 index 번호를 갖게 될 경우, linkedlist 처럼 포인터를 사용해서, head에 새로운 값을 넣는 방식이다. 

Linear probing은 기존의 배열의 빈칸에 key-value를 넣는 것이다. 즉 index 번호가 동일한 경우, 그 index 번호에서부터 다음 index번호로 이동하며, 비어 있는 배열에 넣는다. 만약 배열의 크기를 벗어난다면, 맨 앞으로 돌아가거나, false를 리턴할 수 있다.