해쉬테이블 구현하기(C, C언어)

//
// Created by Eun jung Bang on 2022/12/15.
//

해쉬에서 충돌이 일어났을 때 해결하는 방법
해쉬 충돌:
두 개 이상의 원소들이 동일한 셀로 매핑되는 경우.
1. 분리 연쇄법
리스트를 이용해서 해당 셀에 이어서 연결한다.
2. 개방 주소 법
        a. 선형 조사법: 바로 비어있는 다음 셀에 저장한다. (h(k) +i) . 1차 군집화의 위험
b. 2차 조사법: 제곱만큼 넘어가서 다음 셀에 저장 (h(k) + i^2),. 절반 이상 차면 버켓이 비어있어도 찾기 어려워짐.
c. 이중 해싱: 다른 해싱 함수의 값만큼 넘어가서 다음 셀에 저장. (h(k) + i * h'(k)).h'의 개산 결과가 0이 아니어야 하고 m과 h'가 서로소.

개방주소법 알고리즘
Alg findElement(k)
input A[0..M-1], 해쉬함수 h, key k
output key k에 대한 element

1. v <- h(k)
2. i <- 0
3. while (i < M)
b <- getNextBucket(v, i)
if(isEmpth(A[b])
return NoSuchKey
else if(k = key(A[b]))
return element(A[b])
else
i <- i + 1
4. return NoSuchKey


        Alg insertItem(k, e)
1. v <- h(k)
2. i <- 0
3. while (i < M)
b <- getNextBucket(v, i)
if(isEmpty(A[b]))
Set bucket A[b] to (k, e)
return
else
i <- i + 1
4. overflowException()
5. return

Alg getNextBucket(v,i)  //linear probing
1. return ((v + i)%M)

Alg getNextBucket(v, i) //quadratic probing
1. return (v + i**2)% M

        Alg getNextBucekt(v, i)//double hashing
1. return (v +i*h'(k)) % M

Alg initBucketArray()
input bucket array A[0..M-1]
output bucket array A[0..M-1] 0으로 초기화 되어있다.
1. for i<- 0 to M-1
A[i].empty <- 1
2. return

Alg isEmpty(b)
input bucket b
        output b가 비어있는지 여부 반환
1. return b.empty

        * 개방주소법에서 셀을 임의로 삭제하고 나면, nextBucket으로 접근하다가 비어있는 셀을 만나면 탐색을 종료하기 마련이다. (그 이후 셀에도 없다고 생각)
이를 방지하기 위해, 활성화 라벨을 이용할 수 있다.
탐색 시에는 활성또는 비활성 라벨일 동안 접근하다가 비어있는 셀을 만나면 탐색을 종료하고, 활성 셀에서 원소를 찾는다.
삽입 시에는 삽입할 위치를 비어있는 또는 비활성 셀들을 찾아 삽입하고, 활성셀로 바꿔준다.
삭제 시에는 삭제할 원소를 활성 셀에서 찾다가 비활성으로 바꾸어준다. 비어있는 셀을 만나면 탐색 실패로 종료한다.

* 적재율의 개념
적재율 = n/ M. 좋은 해쉬 함수를 만나면 findElement, insertItem, removeItem 메소드가 이값만큼의 big-O를 가진다.
분리 연쇄법을 사용하는 경우 적재율이 1보다 크면 다소 비효율적이다.
개방 주소법을 이용하는 경우엔 적재율이 항상 1이하이다.
0.5이하의 적재율이면 O(1)기대시간을 만족하게 되고, 그보다 크면 선형, 2차조사법의 경우 군집화가 발생할 수 있으며 이에 따라 성능이 저하될 수 있다.

*재해싱:  적재율을 0.75 수준이하로 유지하기 위해, 재해싱을 사용한다. 즉 원소를 삽입할 때마다 이 한계를 넘기지 않기 위해 추가적인 작업이 요구된다.
재해싱을 하는 경우는 다음과 같다.
a. 적재율의 최적치를 초과
        b. 삽입이 실패
c. 너무 많은 비활성 셀이 포화되어 성능 저하.

재해싱의 방법은 다음과 같다.
1. 버켓 배열의 크기를 증가시킨다.(단 배열의 크기는 소수여야 한다.)
2. 새 크기에 대응하도록 압축맵을 수정
3. 새 압축맵을 사용하여 기존 해시테이블의 원소들을 새 테이블에 삽입.

*최악의 경우 해시테이블에 대한 탐색, 삽입, 삭제는 O(n)만큼 걸린다.
*사전에서 해쉬를 사용할 경우 기대시간은 O(1)이다.
*개방주소법에서 삽입을 위한 기대 조사 횟수는 1/1-적재율이다.