[Datastructure]Hash Table

Hash Table

Hash Table은 key 를 이용하여 value를 저장하고 가져올때 빠르게 가져올수 있는 자료구조이다.

해시함수에 key값을 input으로 주면 해시함수에서 어떤 특정한 값을주게 된다. 그 값을 array의 index로 사용하여 값을 저장하게 된다.

이렇게 되면 같은 값으로 data를 찾을때 시간복잡도가 상수시간을 따르기때문에 매우 빠르게 검색이 가능하게 된다.

---

해시충돌

Separate chaining 방식

해시테이블은 다른 key값을 넣어도 같은 해시값을 가지고 동일한 array의 index으로 값을 넣어버릴수가 있다. 이렇게되면 이전값은 새로 온 값에 아마 지워질것이다. 

이런 문제를 해결하기 위해 해시태이블에 array의index값에 새로운 노드를 만들어 linked list 자료구조를 이용, 해당 index에서 온 값들을 서로 연결시켜 가진다.

Join Smith와 Sandra Dee 가 해싱함수를 거쳐 array의 index가 152가 나온 상황이다. 이러한 충돌이 발생한 경우 버킷(array)에서 linked list를 구현하여 충돌을 해결해 준다.