Hash Table은 진짜진짜 중요한 자료구조!
엄청 유용하고 코드를 빠르게 만들어줌!

Hash Table

Hash Table은 Key Value System을 이용해서 자료를 정리한다.
Key Value System의 예시로는 사전이 있다. 사전에서 단어를 찾고 (=Key) 해당 단어의 뜻과 설명 (=Value)을 확인할 수 있다.

Hash Table vs Array

Array

레스토랑의 메뉴를 배열에 저장할 경우 다음과 같이 저장될 것이다.

menu = [
  {name: "coffee", price: 10},
  {name: "burger", price: 15},
  {name: "tea", price: 5},
  {name: "pizza", price: 10},
  {name: "juice", price: 5},
];

여기서 'pizza'의 가격을 찾으려면 선형검색(Linear Search)을 해서 찾을 수 있지만 시간이 많이 소요된다.

Hash Table

같은 메뉴를 Hash Table로 저장할 경우 다음과 같이 저장된다.

menu = {
  coffe: 10,
  burger: 15,
  tea: 5,
  pizza: 10,
  juice: 5,
};

따라서 이 경우 pizza의 가격을 알고 싶다면, pizza는 key가 되고 Hash Table은 가격을 value로 제공한다.

시간복잡도

배열로 가격을 찾는 방법은 O(N)인 것에 반해, Hash Table로 가격을 찾는 방법은 O(1) 즉 Constant Time(상수 시간)이다.
즉, 그 어떤 메뉴의 가격을 찾더라도 소요되는건 딱 한 개 스텝이다.

Hash Table 활용하기

나라들이라는 배열에서 태국이 해당 리스트에 있는지 체크하고 싶다면, 선형검색을 해야 하고 시간이 오래 걸린다.

이를 개선하기 위해서 국기를 key로 갖고 true를 value로 갖는 Hash Table를 만든다.

이렇게 구현할 경우 해당 나라를 찾을 때 딱 한 번의 스텝만 필요하다.

Hash Table 작동원리

Hash Table에는 array 구조가 있다. 모든 Hash Table 값들은 이 구조에 있다.
같은 array 구조임에도 불구하고 Hash Table이 더 빠른 이유는 'Hash Function' 때문이다.

Hash Function이 저장하고 싶은 key를 숫자로 변환한다.

해당 숫자 = index가 되어 그 index에 value가 저장된다.

Hash Conflict (Hash 충돌)

각기 다른 key에 대해 해시함수가 동일한 숫자를 준 경우를 의미한다.
이런 경우에 여러 대처 방법이 있는데 그 중 하나는 같은 위치에 또 다른 배열을 넣는 것이다. 해당 위치의 배열 내에서 선형검색을 실행하게 된다. 따라서 Hash Table은 언제나 항상 상수시간은 아니다.