견습공

Hash Table

해시 테이블은 단순한 표현인 배열을 일반화 한것이라 할 수 있다.
일반적인 배열에 대한 직접 번지화 방법은 배열의 임의의 위치를 O(1)에 접근하는 효율적인 방법이다.
해시 테이블은 마찬가지로 직접 번지화 방법을 이용한다.
다만 차이점이 있다면 해시 테이블의 경우 키를 배열의 인덱스로 사용하지 않고 키로부터 계산한 값을 인덱스로 사용한다.

만약 서로 다른 여러 키로부터 계산된 인덱스 값이 동일할 경우 충돌이라고 하고 이를 해결하기위해 적절한 해시 함수를 작성하거나, 체이닝, open-addressing 등 을 이용한다.
여기서 적절한 해시 함수란 결국 m개의 공간에 n개의 데이터가 골고루 해시되게하는 함수를 의미한다.

체이닝
- 같은 위치에 해시되는 원소들을 리스트의 형태로 넣는 방법. 이를 통해 충돌을 처리 할 수 있다. 체이닝을 했을때의 작동 시간은 각각 얼마의 저장공간을 가지고 몇개가 저장되어있는지가 관건이다. 총 n 개의 데이터가 모두 같은 위치에 해시 될경우가 최악의 경우라 할 수 있다.
m개의 저장공간을 가지고 n개가 저장된 해시테이블의 적재율은 n/m으로 정의된다.
m개의 위치에 골고루 해시된다고 할 때 이러한 것을 단순 균등 해싱이라고 한다.

Open-addressing
open-addressing기법은 체이닝과 달리 모든 원소들이 해시 테이블에만 저장되는 특성을 가진다.따라서 적재율은 절대 1을 넘을 수 없다.
 해시 테이블에 데이터를 삽입할 경우 해시함수를 통해 데이터를 삽입하고 만약 그 공간이 다른 데이터로 채워져있을경우 키를 저장할 빈 공간을 찾을때까지 해시테이블을 연속해서 조사해나간다.
이러한 방법으로는 선형조사방법, 2차원조사 방법, 중복 해싱방법이 있다.

선형조사 방법은 h(i, i ) = (h'(k) + i ) mod m 과 같은 식을 이용하는 것으로 i를 0부터 m-1식 선형적으로 증가시키며 빈공간을 찾아간다. 구현하기 쉬우나 하나의 영향으로 여럿이 collision되는 primary clustering이 단점이다.

2차원 조사(Quadratic probing)의 경우 h(k,i) = (h'(k) + c1i + c2i^2) mod m 과 같은 식을 이용한다.

중복해싱 (Double hashing)의 경우 h(k,i) =  (h1(k) + i* h2(k))mod m 과 같은 식을 이용하여 계산한다.