Hashing

Hashing을 할 때 문제가 되는 것은 중복키이다.

2가지 해결 방법이 있는데 ,  chaining과 open addressing이다

1. Chaining

중복된 값일 경우, 각 칸을 연결리스트로 구현한다.

2. Open Addressing

중복된 값일 경우, 특정 규칙(linear,quadratic,double hashing 등)에 의해 빈칸이 나올 때까지 칸을 찾는 방법이다.

linear probibg의 경우 clustering의 문제가 발생할 수 있기 때문에, quadratic, double hashing 등의 hashing 방벙이 있다.

Hashing 성능 분석을 위한 가정

simle uniform hashing assumption

키값들이 확률적으로 Hashing 값에 동등하게 Mapping 된다는 가정이다. 하지만 hash funciton은 deterministic하므로 현실적으로는 불가능한 이야기이다.

Divsion

해쉬 값을 2^m 으로 나눈 나머지라고 할 경우, 입력값의 하위 m bit가 Hashing Value가 된다