해시 테이블

정의

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조

 

---

특징

• 요소의 추가는 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행
• 테이블의 인덱스는 Bucket 이라고 함
• 테이블의 각 요소는 키-값을 둘 다 저장
• Hash: 해쉬 브라운의 해쉬와 같은 단어이며 고기와 감자를 잘게 다져 요리하듯,
  입력받은 키를 잘게 잘라 숫자로 만든다는 점에서 유사

---

해시 함수

• 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
• 해시 함수의 결과가 동일하다면 해시 충돌 발생

---

해시 충동 해결 방법

• 선형 탐사법: 충돌이 발생하면 인덱스를 옆으로 한 칸 이동
  단순하지만 데이터가 몰릴 수 있다는 단점이 있으며 충돌이 연속해서 발생하면
  계속해서 옆으로 이동하게 됨
  최악의 경우에 탐색에 O(n)이 소요될 수 있
• 제곱 탐사법: 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
  충돌할 수록 간격이 멀어지므로 선형 탐사법에 비해 데이터가 몰리게 될 가능성이 적음
• 이중 해싱: 충돌이 발생하면 다른 해시 함수를 이용
  두 번째 해시 함수를 이용한 경우에도 충돌이 발생하면 두 번째 함수로 인덱스를 연속 생성
• 분리 연결법: 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가
  충돌이 발생한 버킷에 그대로 요소를 추가함
  하나의 버킷이 무한정 늘어날 수 있다는 단점이 있음

---

어디에 사용하는가?

• 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋음
• 배열은 [추가/삭제]에, 연결 리스트는 [탐색]에 O(n)의 시간이 소요되는 반면
  해시 테이블은 각각의 작업에서 모 O(1)의 시간이 소요됨

---

Javascript 에서 해시 테이블 사용

• 객체 리터럴({ }) 사용
• Map 객체 생성 후, get, set 메서드로 요소 검색/추가 가능
  기본 객체와는 다르게 객체/배열 등의 복잡한 타입도 키로 사용 가능
• Set 객체 사용, Set 은 키와 값이 동일하게 저장되는 방식을 채택
  일종의 집합 연산이라고 볼 수 있으며, 중복 요소를 모두 제거할 때 사용 가능