해싱함수

해싱함수 : 키 값을 원소의 위치로 변환하는 함수

해시 테이블 : 해싱 함수에 의해 계산된 주소의 위치에 항목을 저장한 테이블

┗N개의 버킷, m개의 슬롯으로 구성

 

-거의 사용하지 않는 키 값도 있기 때문에 키값의 수만큼 많은 버킷을 만들면 메모리 낭비이다.

그래서 버킷의 수를 줄이고 같은 버킷안에 여러 개의 슬롯을 두어서 해싱함수로 만든 주소가 같으면 같은버킷에 저장한다.

 

Collision

키값이 서로 다른데 버킷주소가 같은 경우 -> 비어있는 슬롯도 없을경우 => 오버플로우 발생

    , 

해싱함수

- 계산이 쉬워야함

- 충돌이 적어야 한다.

- 골고루 분포할 수 있게 만들어야함

 

1)중간 제곱 함수

제곱한 값의 중간 비트들은 키의 모든값과 관련이 있기 때문에 서로다른 값을 갖는다.

주소로 사용하는 비트수는 해시테이블의 버킷의 개수에 따라 결정

2)제산 함수

M으로 나눈 나머지를 이용. M은 적당한 크기의 소수(M은 해시 테이블의 크기)

3)접지 함수

키값의 비트수 > 해시테이블의 인덱스 비트수 일 때 주로 이용

키값을 인덱스의 비트수에 맞게 나누어 계산함.

해싱함수는 여러가지가 존재한다.

오버플로우 처리

1.  선형개방 주소법

버킷에 빈 슬롯이 없으면 그 다음 버킷들에 빈자리를 조사한 뒤 저장한다.

2. 체이닝

 

각 버킷에 하나 이상의 키값을 저장. 각 버킷에 대한 헤드노드는 1차원 배열이고, 슬롯은 헤드에연결리스트로 이어간다. 검색시는 버킷의 연결리스트를 선형검색한다.

[출처] 해싱|작성자 튜기