알고리즘 문제 풀다가 해시 복습 겸 정리

Hashing

정의

키(key; 저장될 값)에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하여 탐색하는 방법

---

Dictionary

해싱은 사전(Dictionary) 자료구조를 구현할 때 사용됨.
사전은 map, table로 불리기도 한다.
dictionary : (key, value) << 이렇게 두 가지 값을 동시에 저장한다.

ADT

• add(key, value)
• delete(key)
• search(key); 탐색은 해싱에서 가장 중요한 연산이다!

---

해싱은 주로 배열을 사용하여 데이터를 저장한다.
그러니까 원하는 항목의 위치만 알고 있으면 빠르게 접근이 가능하다는 점!

해시함수

• 해시함수의 역할
  1. 키를 입력받음
  2. 해시 주소 생성
  3. 생성된 해시 주소를 해시 테이블의 인덱스로 사용

• 좋은 해시함수의 조건
  1. 적은 충돌
  2. 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 함
  3. 빠른 연산

---

해시테이블

해시테이블은 버킷(bucket)으로 이루어지는 테이블이다. 하나의 버킷은 s개의 슬롯(slot)을 가질 수 있으며(그러나 대부분의 경우 하나의 버킷에 하나의 슬롯을 가짐), 하나의 슬롯에는 하나의 항목이 저장된다.

그렇지만 대부분의 경우 해시 테이블의 버킷 수가 모든 키의 경우의 수보다 작으므로 같은 해시 주소로 매핑되는 경우가 자주 발생한다. 서로 다른 두 개의 키 k1과 k2에 대하여 h(k1) = h(k2)인 경우를 충돌(collision)이라고 한다. 이렇게 충돌이 발생하면 같은 버킷에 있는 다른 슬롯에 항목을 저장하게 된다.

그런데!! 이렇게 충돌이 계속 발생하게 되면 결국 버킷에 더 이상 항목을 저장할 수 없게 된다..
즉, 오버플로우(overflow) 발생 ㅠㅠ

---

오버플로우 해결법

1. 개방 주소법(open addressing)

방법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다.
컨셉 : 충돌이 발생한다면 해시 테이블의 비어있는 공간이 나올 때 까지 계속해서 조사한다.

2. 체이닝(chaining)

방법 : 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다.
컨셉 : 원래 해시 함수와 다른 새로운 해시 함수를 이용해서 키를 균일하게 분포시킴. 각 버킷에 고정된 슬롯을 할당하는 것이 아닌, 각 버킷에 삽입/삭제가 편리한 연결 리스트를 할당하여 구현한다.