11강. 해쉬 알고리즘(2)

[ 목차 ]

1. 오픈 어드레싱

2. 선형 프로빙

3. 삽입 연산

4. 해쉬 삽입의 Pseudo Code

5. 해쉬 검색의 Pseudo Code

6. 해쉬 삭제

7. 세 가지 오픈 어드레싱 기술

8. 선형 프로빙

9. 선형 프로빙 장단점

10. 이차식 프로빙

11. 이차식 프로빙의 단점

12. 이중 해싱

13. 이중해싱의 주의점

 

1. 오픈 어드레싱

1) Collision을 피하기 위한 다른 방법으로 key를 hash table에 직접 저장

2) 포인터를 사용하지 않아도 되므로 구현이 간편

3) 포인터를 사용하지 않으므로 추가 메모리 공간 사용이 가능

4) 공간의 충돌 문제가 줄어들며 자료 검색이 미세하게 빨라짐

5) 자료를 직접 기록하는 방법으로 검색, 삽입, 삭제가 빠르지만 충돌의 가능성이 있어서 리니어 프로빙, 쿼드라틱 프로빙, 더블 프로빙의 방법을 사용해 충돌을 최소화할 필요가 있음

 

2. 선형 프로빙

1) 다음과 같은 조건이 주어졌을 때 선형 프로빙으로 key값을 테이블에 저장

2) m = 13, k = {5, 14, 29, 25, 17, 21, 18, 32, 20, 9, 15, 27}

3) h(k) = k mod 13

4) 충돌이 일어날 경우 다음 칸에 저장

 

3. 삽입 연산

1) 빈 slot이 나올 때까지 해쉬 테이블을 탐색

2) key가 삽입되는 형태에 따라서 빈 slot의 위치가 결정

3) 모든 key값에 대해 탐색 순서는 <0, 1, .., m-1>에 대해 <h(k,0), h(k,1), ..., h(k-1)>을 탐색

 

4. 해쉬 삽입의 Pseudo Code

 

5. 해쉬 검색의 Pseudo Code

 

6. 해쉬 삭제

1) 실제로 값을 지우는 경우 DELETED 라고 표시

2) 빈 slot이 있는 경우 원래 값이 있어쓴데 지워서 비어있는지 원래 값이 없어서 빈 slot인지 구분할 수 없기 때문

3) 순차 검색에서 비어있는 공간이 나오면 그 이후는 찾아보지 않기 때문에 값이 있음에도 찾지 못할 수 있음

 

7. 세 가지 오픈 어드레싱 기술

1) 선형 프로빙

2) 이차식 프로빙

3) 이중 해싱

 

8. 선형 프로빙

1) 일반적인 해쉬 함수 h' : U ->{0, 1, ..., m-1}가 주어졌을 때 보조 해쉬 함수를 사용해서 선형 프로빙을 하는 방식

2) k(k,i) = (h'(k) + i) mod m

3) i = 현재 키값이 충돌한 횟수

3) 선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈 slot을 찾는 작업을 반복

 

9. 선형 프로빙 장단점

1) 구현은 매우 쉬우나 primaty clustering 문제가 존재

2) 값이 들어있는 slot의 수가 많으면 평균 검색시간 증가

3) key 값을 넣을 빈 slot은 뭉쳐있는 slot들의 끝부분에 존재하기 때문에 값이 들어있는 slot들이 뭉쳐있는 경우가 많음

 

10. 이차식 프로빙

1) h(k,i) = (h'(k) + c1i _ c2i제곱) mod m

2) h'는 보조 해쉬 함수이고 c1과 c2는 0이아닌 상수

3) 주어진 hash 함수 외에 i에 대한 2차함수 꼴로 slot을 이동하면서 빈 slot을 찾음

4) 다음과 같은 조건이 주어졌을 대 이차식 프로빙으로 key값을 테이블에 저장

5) m = 13, k = {5, 14, 29, 25, 17, 21, 18, 32, 20, 9, 15, 27}

 

11. 이차식 프로빙의 단점

1) 두 key의 처음 probe 값이 동일하다면 빈 slot을 찾는 과정이 동일하므로 같은 slot을 탐색

2) h(k1,0) = h(k2,0)이면 h(k1,i) = h(k2,i)이기 때문이며, 이를 secondary clustering이라고 지칭

3) 처음 충돌한 위치가 같다면 다음 충돌할 위치에서도 반복적으로 계속 충돌

4) 처음 시작 값이 같으면 매번 계산할 때마다 이전의 key 값과 동일한 위치만큼 이동하기 때문

 

12. 이중 해싱

1) h(k,i) = (h1(k)+i + h2(k)) mod m

2) 처음 탐색하는 위치는 T[j1,(k)]

3) 다음부터는 h2(k) modulo m만큼 이동하면서 탐색

4) 충돌이 발생했을 때 이동하는 거리가 hash 함수에 의해 계산되어 무작위로 빈 slot을 찾음

5) 다음과 같은 조건이 주어졌을 때 이중 해싱으로 key 값을 테이블에 저장

 6) m = 13, k = {5, 14, 29, 25, 17, 21, 18, 32, 20, 9, 15, 27}

 

13. 이중해싱의 주의점

1) h2(h) 함수는 테이블의 크기 m과 서로 소 관계여야 함

2) 이것을 만족하는 가장 쉬운 방법은 m을 2의 주수승으로 두고 h2가 항상 홀수가 되도록 하는 것

3) 다른 방법은 m을 소수로 하고 h2를 m보다 작은 양수로 하는 것