Map & Hash Table

Hashing

정의

해시 함수를 사용해 key, value를 해시 테이블에 매핑하는 기술이다.

구성 요소

• key
  • 해시에 입력으로 제공되는 문자열 또는 정수
  • 데이터 구조에서 항목을 저장하기 위한 인덱스나 위치를 결정하는 기술에 사용된다.
• hash function
  • 입력 키를 받아 해시 테이블의 요소 인덱스을 반환하는 함수
  • 인덱스는 hash index로 불린다.
• hash table
  • 해시 함수라는 특수 함수를 사용해 key를 value에 매핑하는 데이터 구조
  • 각 데이터 값이 고유한 인덱스를 갖는 배열에 데이터를 저장

hashing 예시

해시 함수가 h(k) = k mod 7인 경우

충돌 처리

1. seperate chaining
   • 가장 유명한 충돌 처리 방법 중 하나
   • chain이라 불리는 linked list를 사용해 구현
   • 이 방식은 동일한 인덱스로 해시되는 모든 요소를 linked list에 삽입하는 방식을 사용한다.
   • 체인이 길어지면 O(n)의 시간 복잡도를 갖는다.
2. open addressing
   • 선형 탐사법
     • 충돌이 발생 할 경우 빈 슬롯이 나올 때까지 탐색 후, 빈 슬롯이 나오면 위치를 결정
     • 일차 군집화에 취약하다.
   • 제곱 탐사법
     • 이차 함수를 활용해 슬롯을 이동하여 위치를 결정한다.
     • 이차 군집화에 취약하다.
   • 이중 해시
     • 해시 값이 충돌이 나게 되면 탐사 이동폭을 얻기 위해 또다른 해시 함수를 추가로 사용하는 방식