[data structure] hash table

hash table

파이썬의 dictionary와 go의 map과 상응한다.

 

ex)

menu = {
   coffee : 10,
   tea : 5
};

key value system을 이용해 자료를 정리한다.
사전을 생각하면 편하다.

---

hash table vs array
array로 저장하면 선형검색으로 원하는 값을 일일이 찾아야하지만
hash table은 원하는 값을 한번에 찾을 수 있다.
삭제할때도 똑같다.

원리
hash function이 key값을 받으면 인덱스값을 준다. 그 인덱스 값으로 밸류값을 찾는다.
그런데 저장을 할 때 같은 인덱스 값을 줄경우가 있는데
그때는 충돌이 일어났다고 표현하며 인덱스값에 배열을 만든다.
우리가 찾을 때는 그 인덱스값의 배열을 찾아가서 선형검색을 한다.