Hash Table 이란?

• key : value 형태로 저장되는 자료구조다
• 시간복잡도는 O(1)
• Array보다 빠르게 저장/삭제/조회가 가능하다

• ex) JS - Object / Go - map / Python - Dictionary

비효율적 방법

밑처럼하면 선형검색으로 O(n) 시간이 오래걸림

나라들 = ["중국", "미국", "한국"]

효율적 방법

그런데 value만 저장하면 O(1)으로 1번의 스텝만 거쳐서 빠르다.

나라들 = {
  "중국":true,
  "미국":true, 
  "한국":true,
}
나라들 = ["중국"]; //true
나라들 = ["하하"] //undefined

작동원리

해시테이블 안에 array구조가 있는데, array보다 더 빠른 이유는 해쉬함수 때문이다.

Hash Function 해시 함수

key값을 해시함수를 거쳐서 buket index번호에 저장한다. 이러한 구조로 데이터를 저장하면 key값으로 데이터를 찾을 때 1번만 찾으면 되므로, 데이터 저장/삭제/조회를 빠르게 할 수 있다.

Collision 해시 충돌

각기 다른 key값에 대해서 해시함수가 동일한 index를 준 경우 충돌이 일어난다.
충돌이 일어난 경우 밑과 같은 방법으로 해결한다.

1. Chaining
2. Open Addressing
   - 선형탐사(Linear Probing)
   - 제곱탐사(Quadratic Probing)
   - 이중해싱(Double Hashing)
   
   
   
   
   

참고

그림 출처