[자료구조] 해싱(Hashing)

: 자료를 검색할 때, 탐색이나 첨자가 아닌, 내용에 의해 필요한 자료에 도달하는 기법

 > 사전 찾아보는거랑 비슷함.

 > 해시 테이블을 이용해 탐색을 수행한다. (자료가 해시테이블에 저장됨)

 > 자료를 찾아주는 함수를 해싱 함수라 한다.

 > 서로 다른 자료가 해싱 함수에 의해 같은 값을 생성하는 경우, 충돌(Collision)이라고 한다.

 > 탐색 시간이 O(1)에 가깝다! (엄청 빠르제?)

 > 공간 사용률이 70% ~ 80% 에 이르면 성능 저하가 나타난다! (공간을 포기하고 성능을 선택한다!)

* 해싱 함수(Hashing Function)

: 어떤 키 K에 대한 테이블의 주소를 계산하기 위한 방법

  > 주어진 키 값으로부터

레코드(원하는 자료)가 저장되어 있는 주소

를 산출해낼 수 있는 공식!

 - 충돌(collision) : 해시함수 H(K)에 대해서, H(k1) = H(k2) 인 경우.

> 즉 다른 자료가 같은 주소를 만들어 내는 경우

 - 동의어(synonym) : H(k1) = H(k2)인 경우, k1과 k2 는 동의어 이다.

> 즉, 같은 주소를 만들어 내는 둘 이상의 자료

* 용어 정리

- 버킷(Bucket)  : 하나의 주소를 갖는 한 구역

- 슬롯(Slot)  : 하나의 레코드를 저장할 수 있는 공강

- 오버플로(Overflow)  : 한 홈 주소의 버킷 내에 더 이상의 레코드를 저장할 슬롯이 없는 상태

* 해싱 함수의 종류 : 나눗셈법, 자릿수 접기법, 제산법, 숫자 분석법, 제곱법 등이 있다.

1. 나눗셈 법(Division Method)

: 자료를 테이블의 크기로 나누고, 그 나머지를 테이블의 주소로 사용한다.

 > 주소 = 자료값 % 테이블의 크기  (테이블안에 자료를 우겨넣기 위한 처절한 노력...)

 > 테이블의 크기는 소수(Prime Number)로 정하는 것이 좋다고 알려져 있다.

2. 자릿수 접기(접기법, Folding)

: 숫자의 각 자릿수를 더해 해시 값(주소)을 만든다. (접기보단 겹치기가 더 잘어울리는데...?)

 > 문자열을 키로 사용하는 해시 테이블의 경우 잘 어울림

 > HELLO => 72(H) + 101(e) + 108(l) + 108(l) + 111(o) = 500

* 충돌 해결!(Collision Resolution) : 해싱 함수가 충돌을 일으키면 어떻게 할까?

- 분류

1. 개방해싱(Open Hashing)

: 기존 테이블 외의 새로운 공간을 할당하여 문제 해결

 > ex) 체이닝

2. 폐쇄 해싱(Closed Hashing)

: 기존 테이블 내에서 문제 해결

 > ex) 체이닝, 개방 주소법(Open Addressing)

>개방 주소법의 종류 : 선형탐사(linear), 제곱탐사(Quadratic), 이중해싱(Double Hashing), 재해싱(Rehasing)

- 해결 방법

1. 체이닝(Chaning)

: 해시 테이블에 링크드 리스트를 삽입하여 충돌이 일어난 자료를 저장

 > 새 데이터를 리스트 맨 앞에 저장한다. (마지막에 저장하면 리스트 끝까지 찾아가야함

 > 자료 찾는데에는 시간이 좀 걸림 > 이진 탐색트리를 활용하면 오우 예~

2. 개방 주소법(Open addressing)

 ㄱ. 선형 탐사 (Linear Probing)

  : 충돌 발생시, 정해진 칸수 다음에 저장(자료 찾을 때 없으면 다 뒤져봐야함)

 ㄴ. 제곱 탐사(Quadratic Probing)

  : 선형 탐사에서 정해진 칸 수가 제곱수로 늘어남 (2의 제곱, 3의 제곱으로 늘어나나..?)

 ㄷ. 이중해싱(Double Hashing)

  : 2개의 해시함수를 사용. 하나는 최초의 주소를 얻기 위해, 또 하나는 충돌시 탐사 이동폭을 얻기 위해

 ㄹ. 재해싱(Rehashing)

  : 해시 테이블을 늘리고, 늘어난 해시 테이블의 크기에 맞춰 자료를 다시 배열