Hash Table

본 내용은 노마드 코더님의 강의를 토대로 작성하였습니다.

 

1. Hash Table이란?

• Key Value System을 이용하여 자료를 정리
  • 사전

 

Hash Table Vs. Array

• 레스토랑의 매뉴를 배열로 정리하면 아래와 같음
  • 한 메뉴의 가격을 찾기 위해서는 선형 검색을 통해서 찾아야 함
  • O(N)의 시간 복잡도를 가짐

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

•  
• 위 레스토랑의 메뉴를 Hash Table로 정리하면 아래와 같음
  • 한 메뉴의 가격을 찾기 위해 key를 사용하여 빠르게 찾을 수 있음
  • O(1)의 시간 복잡도를 가짐
  • 어떤 메뉴를 찾더라도 한 개의 단계만이 필요함
  • 요소를 추가 또는 삭제를 할 때도 시간 복잡도는 O(1)
• Array 비교하여 월등히 빠름

const menu = {
  coffee: 10,
  burger: 15,
  tea: 5,
  pizza: 10,
  juice: 5,
}

 

2. Hash Table의 작동 원리

• Hash Table에는 Array 구조가 있음

 

Hash Function

• Hash Table이 Array 구조가 있음에도 불구하고 Array보다 월등히 빠른 이유
• Hash Function이 저장하고 싶은 Key를 index로 변환
• Hash Function이 key를 전달받으면 해당하는 index로 변환하여 value를 가져옴

 

Collision(해시 충돌)

• 각기 다른 Key에 대하여 Hash Function이 동일한 숫자를 준 경우
• 대처 방법은 2가지
• 같은 공간에 또 다른 배열을 넣음
  • 단 이 경우는 같은 공간의 요소를 찾을 때 선형 검색으로 찾아야함
  • 그러므로, Hash Table의 요소 접근이 항상 상수 시간을 가지는 것은 아님

 

Reference

[노마드코더] 개발자라면 꼭 알아야할 Hash Table 의 모든 것!