해싱

해싱

해싱: 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾아가는 검색 방식

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

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

 

동일한 해시 주소를 가지면 충돌이 일어난다.

 

해시 함수

-해시 함수의 조건

해시 함수는 계산이 쉬워야하고 충돌이 적어야한다.

헤시 테이블에 고르게 분포할 수 있어야한다.

 

-중간 제곱 함수

예를 들면 제곱하여 중간 자리 수에 있는 값을 해시 주소로 사용한다.

 

-제산 함수

나머지 연산이다.

10, 7, 77, 9를 각각 8로 나누고 그 나머지를 해시 주소로 사용한다.

 

-승산 함수

키 값 k와 정해진 실수 α를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 그 정수 값을 주소로 사용한다.

 

-접지 함수

1. 이동 접지 함수

해시 테이블 인덱스가 3자리고 키 값 k가 12312312312이면 

123 123 123 12로 나누고 다 더한다. 그러면 381이 해시 주소

 

2. 경계 접지 함수

12312312312가 있으면 123 321 123 21 이런식으로 하는 원래대로, 다음은 반대로 잘라서 더한다.

따라서 588이 해시 주소

 

-숫자 분석 함수

예를 들어 학번을 기준으로 하면 앞에 몇 자리는 공통된 점이 있다.

이런 겹치는 수를 제거하고 해시 주소를 만든다.

 

-진법 변환 함수

기수 변환법이라고도 한다.

38, 12, 76이 있고 2진법으로 표현하면

38 => 3*2^1 + 8*1 = 14

12 => 1*2^1 + 2*1 = 4

76 => 7*2^1 + 6*1 = 20

이렇게 나온 값이 주소값이다.

 

진수에 따라 곱하기를 다르게 하면된다.

 

오버플로 처리 방법

-선형 개방 주소법(선형 주소법)

오버플로가 발생하면 옆에 슬롯을 본다.

 

-예시

1. 1차 조사법

보통은 해시 테이블의 크기로 나눈다.

이런식으로 넣다가 충돌이 일어나면 바로 옆에 넣는다.

 

특정 영역에 원소가 몰려서 안좋다.

 

2. 2차원 조사법

i^2, 제곱을 이용하는 것이다.

이것은 만약 충돌이 일어나고 옆 슬롯이 비어있으면 1^2해서 옆에 넣으면된다.

하지만 옆 슬롯에도 충돌이 일어나면 2^2해서 충돌이 일어난 지점에서 4칸 떨어진 곳에 넣는다.

이런식으로 제곱을 하여 그 수만큼 떨어진 슬롯에 넣는다.

 

2차 군집이 생겨서 안좋다.

 

3. 이중 더블 해싱

해싱 함수를 2번 사용한다.

 

충돌이 안일어나면 해싱 함수 한번만 사용하면 된다.

 

22까지는 충돌이 안일어나서 해시 함수를 한번만 사용한다.

35는 충돌이 발생 => 2차 해시 함수 사용, d(key)하고 (h(key) + j*d(key)) % 13

2차 해시 함수는 보통 1차 해시 함수보다 작은 수로 나눈다. 그리고 나누고 나눈 값에서 빼준다. 그리고 (h(key) + j*d(key)) % 13이렇게 한다. j는 1부터 충돌이 안일어날때까지 증가한다. 

 

4. 체이닝

연결리스트를 이용하여 오버플로를 처리한다.