값
으로 결정하는 자료구조성질
충돌
충돌 처리
는 해시 테이블 이론의 핵심이며, 해결 방법이 여러가지이다.적재율
__table[]
🠔 해시 테이블로 사용하는 배열__numItems
🠔 해시 테이블의 원소 개수
search(x)
🠔 해시 테이블에서 원소 x를 검색한다.insert(x)
🠔 해시 테이블에 원소 x를 삽입한다.delete(x)
🠔 해시 테이블에서 원소 x를 삭제한다.isEmpty()
🠔 해시 테이블이 빈 상태인지 알려준다.clear()
🠔 해시 테이블을 깨끗이 청소한다.
해시 함수
입력 키를 해시 테이블 전체에 고루 분산시켜 저장해야 한다.
h(x) = x % m
m
: 해시 테이블의 크기x
: 삽입할 원소의 Key2의 멱수
에 가깝지 않은 소수`를 택하는 것이 좋다.h(x)=⌊m(xA%1)⌋
m
: 해시 테이블의 크기x
: 삽입할 원소의 KeyA
: 해시 함수의 특성값 (0<A<1)Hash Table Structure의 고질병인 Colision을 해결하는데에는
크게Chaining(체이닝)
과Open Addressing(개방 주소)
방법이 있다.
chainedHashInsert(T[], x) { // T: 해시 테이블 // x: 삽입 원소 리스트 T[h(x)]의 맨 앞에 x를 삽입 } chainedHashSearch(T[], x) { // T: 해시 테이블 // x: 검색 원소 리스트 T[h(x)]에서 x값을 가진 원소를 검색 } chainedHashDelete(T[], x) { // T: 해시 테이블 // x: 삭제 원소 리스트 T[h(x)]에서 x의 노드를 삭제 }
해시 테이블 내에서 충돌을 해결한다.
(추가 공간을 허용하지 않는다.)선형 탐색 방법
, 이차원 탐색
, 더블 해싱
으로 구분된다.적재율(α)이 1
을 초과할 수 없다.Threshold(임계점)
을 설정한 후,hᵢ(x)=(h(x)+i)%m i=0,1,2,⋯
1차 군집
이 발생될 수 있다는 단점이 있다.hᵢ(x)=(h(x)+i+c₁i²+c₂i)%m i=0,1,2,⋯
2차 군집
위의 예시 그림 오른쪽
hᵢ(x)=(h(x)+i*f(x))%m i=0,1,2,⋯
h(x)=x%m
f(x)=1+(x%m′)
DELETED
)을 남겨서 위와 같은 현상을 예방한다.체이닝 방법을 이용하는 해싱에서 적재율이 α일 때,
실패하는 검색에서의 조사 횟수 기대치는 α에 비례한다.
체이닝 방법을 이용하는 해싱에서 적재율이 α일 때,
성공하는 검색에서의 조사 횟수 기대치는 (1+α)/2 + α/2n이다.
개방 주소 방법의 이론적인 성능은 체이닝 보다 못하다.
증명에 대해선 여기서
어느 경우에서든, 적재율이 높으면 해싱 효율을 저해하므로 적절하게 낮은 적재율을 유지해야 한다.