해시
임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것
Direct Addressing Table
key-value쌍의 데이터를 배열에 저장할, key값을 직접적으로 배열의 인덱스로 사용하는 방법이다.
Hash Table
key-value 쌍에서 key값을 테이블에 저장할 때, Direct Addressing Table과 달리 key값을 함수를 이용해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 저장하는 방식이다.
충돌
해시 테이블은 다른 k값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 충돌이 일어날 수 있다는 문제점이 있는데,
충돌을 완전히 방지는 힘들기 때문에 최소화 하는 방법을 사용한다.
Chaining방법
충돌을 허용하지만 최소화하는 방법 중 하나이다. 해시 테이블에서 동일한 해시값이 출력되어 충돌이 일어나면,키의 해시 값을 계산하고, 해시 값을 이용해 배열의 인덱스를 구하고, 같은 인덱스가 있다면 연결 리스트로 연결한다.
Open Addressing
충돌 발생 시 테이블 공간을 탐사해 빈 공간을 찾아나서는 방식이다.
Liner probing
Open Addressing 방식으로, key값으로 인덱스를 계산할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다.
Quadratic probing
Open Addressing 방식으로, primary clustering을 방지하기 위해 hash함수를 다음과 같은 2차식의 형태로 만드는 것이다.
h(k,i)=(h'(k)+c1i+c2i^2)mod m
Double hashing
Open Addressing 방식으로, Quadratic probing의 secondary clustering을 해결하기 위해서 사용하는 방법이다. 해시 함수를 다음과 같은 2개로 구성하여 처리한다.
h1(k)=k mod m
h2(k)=k mod m2
h(k,i)=(h'(k)+c1i+c2i^2)mod m
