Hash Collision

하지만 입력 공간이 무한하지 않기 때문에 어떤 시점에서는 서로 다른 입력들이 동일한 해시 값으로 매핑될 수 있습니다.

이러한 상황이 해시 충돌입니다

두 개의 입력이 동일한 해시 값으로 매핑된다면, 해시 테이블에서 데이터를 올바르게 검색할 수 없게 됩니다.

Chaining

동일 slot에 연결 리스트로 저장하는 방법

각 해시 테이블 slot T[j]는 해시 값이 j인 모든 키를 연결 리스트로 저장하여 충돌을 해결합니다.

h(k1) = h(k4), h(k2)=h(k5)=h(k6)

체이닝 기본 연산은 다음과 같습니다.

CHAINED-HASH-INSERT(T,x): T[h(x.key)] 리스트에 x를 삽입합니다. CHAINED-HASH-SEARCH(T, k) : T[h(k)] 리스트에 키 k를 찾습니다. CHAINED-HASH-DELETE(T,x): T[h(x.key)] 리스트에 x를 삭제합니다.

장점	단점
구현이 단순	연결 리스트를 사용해 키를 저장하므로 캐시 성능은 떨어지게 됩니다.
연결 리스트로 저장하기 때문에 테이블이 가득 차지 않습니다.	사용하지 않는 slot이 생길 수 있어 공간 낭비가 발생하게 됩니다
해시 함수 및 적재율(load factor)에 영향을 덜 받습니다	한 slot에 계속해서 저장된다면 체인이 길어져 최악의 경우 검색 시간이 O(n)이 될 수 있습니다.
키의 삽입 또는 삭제 횟수와 빈도를 알 수 없을 때 주로 사용됩니다	링크 주소를 저장하기 위해 추가 메모리 공간이 필요합니다

O(1+@) (@ = 적재율(Load factor))

테이블 slot에 접근하기 위해 O(1)의 시간이 걸리고 해당 슬롯에 있는 리스트를 검색하기 위해 O(@)의 시간이 걸리기 때문입니다.

Open Addressing

개방 주소법(Open Addressing)이란 충돌이 일어난 키 값을 비어 있는 다른 주소를 찾아 저장하는 방법입니다.

모든 요소를 해시 테이블 자체에 저장하기 때문에 테이블의 크기는 키의 개수보다 크거나 같아야 합니다.

Linear probing

선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈 slot을 찾는 방식입니다. h(k)→ 충돌 → h(k)+1→충돌→ h(k)+2→...

h`: U→{0,1,..., m-1} 이라면 선형 탐색에서 사용하는 해시함수는 다음과 같습니다. h(k, i) = (h`(k) + i) mod m ( i=0,1...m-1 , m : table size)