해쉬 알고리즘

Direct-Address Tables

- 크기가  |U|인 테이블 T를 생성하고 중복되지 않는 key k를 slot k에 저장하며 key를 이용하여 데이터를 찾아가므로 시간 복잡도가 매우 빠름

- 그러나 actual key(실제로 사용하는 키)크기가 아닌 universe key(실제로 사용하지 않는키들을 포함한)로 테이블을 생성하므로 공간 낭비가 심함

Hashing

- key를 바로 slot에 저장하지 않고 해쉬 함수 h()에 저장한다.

- 그러나 이렇게 하면 다른키가 같은 해쉬 값을 가지게 되는 문제가 생긴다. => "충돌이 발생했다" 라고 한다.

Collision resolution by chaining

- 충돌되는 key들을 저장할때 해당 슬롯을 연결리스트로 저장한다.

- 그러나 이 방법은 최악의 경우 한 버텍스를 찾기 위해서 리스트를 모두 탐해야 하므로 해쉬테이블을 쓰는 의미가 사라진다.

ex. E를 찾기위해 d->f->e 이런식으로 가야한다.

좋은 해쉬 함수?

-좋은 해쉬 함수는 key의 중복 없이 m개의 slot에 동일한 확률로 해쉬되고 다른 key값의 해쉬 값과 관계없이 해쉬된다. ( simple uniform hasing )

해쉬 함수

- 해쉬 함수에서는 key값을 자연수로 가정하고 char,string 형태일경우 자연수 형태로 변형하여 사용(아스키코드)

- 나눗셈 방법 h(k){ k mod M }

- 이때 m은 2의 ^을 피하고 2^-1도 피한다. 왜냐하면 2의 자승은 전체 값에 따라 바뀌지 않고 하위 p비트에만 영향을 해쉬함수가 받는다. 근데 이때 하위 p비트가 평균적으로 골고루 나오지 않기때문에 문제라는 것 (2 ^ -1도 2 ^ 이랑 비슷하기 떄문에 피하라는 것)

해쉬의 삭제

- 실제로 해쉬 값을 빈칸으로 두면 더 이상 값이 없다고 판단하고 탐색을 하지 않기때문에 '값을 삭제했다' 라는 표시를 해둬야함 ex.Del,delete..등

Open Addressing

- 충돌을 피하기 위해 key에 대한 해쉬 함수의 결과를 직접 table에 저장

- 하지만 이것도 충돌이 나는것은 여전함

- 선형 프로빙,Linear probing 방식 : 충돌이 일어나면 index+n의 값에 해당 값을 저장함 ( 이때 n은 빈칸이 나올때까지 이동한 거리 )

- 하지만 그냥 바로 다음칸으로 움직이고 이런 단순함 때문에 value가 존재하는 index가 뭉쳐있는 문제가 발생

- 이차식 방식(Quadratic probing) :

-h'는 보조 해쉬함수 c1,c2는 0이 아닌 상수로 i에 대한 2차함수 꼴로 이동하면서 들어갈 slot을 선정함

(h'(k) +c1i+c2i) mod m

- secondary clustering 문제 발생 : 시작 slot이 같으면 계~속 같은 slot을 이동해서 같은 충돌이 계속 일어남

- 이중 해싱(Double hasing) :

(h1(k) + i * h2(k)) mod m

- h2(k)함수는 해쉬 테이블의 크기 과 서로 소 관계여야한다 안그러면 또 간데 또가고 또 반복이다. 이것을 만족하기 위해선

- m을 2의 지수승으로 두고 h2가 항상 홀수가 되게 만든다.

- m을 소수로 하고 h2를 m보다 작은 양수로 정한다.