해쉬테이블

• 해쉬테이블은 키-주소 매핑에 의해 구현된 사전 ADT
• 사용 경우 : 컴파일러의 심볼테이블, 환경변수 레지스트리
• Bucket (Array) + Function(hash)

성능

• 탐색, 삭제, 삽입 : 최악 : O(n), 기대: O(1)

Bucket Array

• 키가 유일한 정수 이며 [0~M-1]범위에 잘 분포되어 있다면, 탐색,삽입, 삭제에 O(n) 시간.

두가지 중요한 결함

• O(n) 공간으 사용함으로 초기 설정한 크기(M)이 n에 비해 매우 크다면 공간 낭비로 이어질 수 있다.

hash function

• 주어진 형의 키를 고정 범위 [0~M-1]로 매핑

  hash code map (h1) : keys->integer
  compression map (h2) : integer -> [0~M-1]
  즉, h(k) = h2(h1(k))

adjecent hash function이 되기 위한 조건

• 키들을 무작위 하게 분산 시켜야 한다.
• 해쉬 함수의 계산이 상수 시간이여야한다

hash code map 의 종류

• memory address
• integer cast
• component sum
• polynomial accumulation

polynomial accumulation

• p(z) = a0 + a1z + a2z^2 + a3 * z^3...

compression map 의 종류

• division
• multiply, add and divide (MAD)
  ( h2(k) = | ak+ b| % M
  a%M != 0
  )

충돌.

• 두 개 이상의 원소들이 동일한 셀로 매핑.

충돌 해결 알고리즘

분리연쇄법 (seperate chaining)

• 각 버켓은 연결리스트 헤더를 저장.
• 무순리스트 또는 기록파일 방식을 사용하여 구현된 미니사전으로 볼 수 있다.

장단점: 단순하고 빠르다는 장점이 있으나, 테이블 외부에 추가적인 저장공간이 필요하다

개방주소법 (open addressing)

• 충돌 항목을 다른 셀에 저장.

장단점: 분리연쇄법에 비해 공간을 절약하지만, 삭제가 아렵다는 것과 사전 항목들이 연이여 일어나는 군집화 가 발생 할 수 있다.

갱싱
1. 비활성화 전략
empty, active , inactive 의 flag를 따로 관리한다.
2. findElement(k)
empty 셀을 만나면 탐색 실패, active 일때는 반환, inactive는 continue
3. InsertElement(K,e)

if(h[k].flag == empty || f[k].flag == inactive) {
	h[k] = e;
   h[k].flag = active;
}

4. removeElement(k,e)

   if(h[k].flag == empty) return;
   else if(h[k] == e] h[k].flag == inactive;

선형조사법 (linear probing)

• 충돌 항목을 바로 다음의 비어 있는 테이블 셀 에 저장함으로 충돌 처리

2차 조사법 (quadratic probing)

• 다음 순서에 의해 버킷을 조사
• A[h(k)] -> A[h(k) +1^2] -> A[h(k) + 2^2] -> A[h(k) + 3^3] ...
• M이 소수가 아니거나, 버켓 배열이 반 이상 차면, 비어 있는 버켓이 있더라도 찾지 못할 수 있다.

이중해싱 (double hashing)

• 두번째의 해시함수를 h'를 사용하여 다음 순서에 의해 버킷을 조사
• A[h(k)] -> A[h(k) + h'(k)] -> A[h(k) + 2h'(k)] -> A[h(k) + 3h'(k)] ...
• 동일한 해시값을 가지는 키들도 상이한 조사를 수반할 수 있기 때문에 군집화를 최소화한다.
• h'(k)와 M은 서로소야 한다

적재율 (load factor)

• a = n/M
• 적재율은 낮게 유지되어야 한다. (1 이하가 이상적)
• 좋은 해쉬 함수면 탐색, 삽입, 삭제의 기대실행시간 O(a)

분리연쇄법

• 적재율 1 이상이 가능 있음
• a> 1, 비효율적
• a <= 1 (0.75미만)이면 기대실행시간 성취 가능

개방 주소법

• 항상 a<= 1
• a>0.5, 선형 및 2차 조사법인 경우 군집화 발생 가능.
• a<=0.5 면 기대실행시간

재해싱

• 적재율을 0.75 이하로 유지하기 위해, 원소를 삽입할때 마다 이 하계를 넘기지 않기 위해 추가적인 작업 필요
• 적재율의 최적치를 초과했을때, 삽입이 실패한 경우, 너무 많은 비활성 셀들도 포화되어 성능이 저하됬을 때

재해싱 단계

1. 버켓 배열의 크기를 증가시킨다. ( 크기를 소수로 유지 시켜야한다)
2. 새 크기에 대응하도록 압축맵을 수정
3. 새 압축맵을 사용하여, 기족 해시테이블을 모든 원소들을 새 테이블에 삽입