[컴퓨터 알고리즘 기초] 10. 해쉬 알고리즘(2)

학습목표

1. open Addressing 방법에 대해 이해하고 장단점을 파악 할 수 있습니다.

2. Linear probing, Quadratic Probing, Double hashing 방법에 대해 이해할 수 있습니다.

---

1. Open-Addressing 개요

오픈 어드레싱(open Addressing)

오픈 어드레싱이란?

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

오픈 어드래싱의 장점

• 포인터를 사용하지 않아도 되므로 구현이 간편하다.
• 포인터를 사용하지 않으므로 추가 메모리 공간 사용이 가능하다.
  • 공간의 충돌 문제가 줄어들며 자료 검색이 미세하게 빨라진다.

선형 프로빙(Linear probing)

• 특정 조건이 주어졌을때 선형 프로빙으로 key값을 테이블에 저장한다.
  • 해시 테이블의 크기 M이 레코드의 개수 N보다 클 때 사용하는 것으로 동일한 주소로 해시되는 원소가 있으면, 해시 테이블 상의 오른쪽 방향으로 이동하면서 비어있는 공간을 찾은 다음 첫번째로 만나는 빈 공간에 원소를  저장한다.

삽입 연산(Insertion)

• 빈 slot이 나올 때까지 해쉬 테이블을 탐색
• key가 삽입되는 형태에 따라서 빈 slot의 위치가 결정된다.
• 모든 key값에 대해 탐색 순서는 <0,1,...,m-1>에 대해 <h(k,0),h(k,1),...,h(k,m-1)>을 탐색한다.

해쉬 삭제

삭제는 실제로 key값을 삭제하는 것이 맞는가?

• 실제로 값을 지우는 경우는 DELETED 라고 표시한다.
• 왜냐하면 빈 slot이 있는 경우, 원래 값이 있었는데 지워서 비어있는지 아니면 원래 값이 없어서 빈 slot인지를 구분할수없기 때문이다.
• 순자검색에서 빈어있는 공간이 나오면 그 이후는 찾아보지않기 때문에 값이 있음에도 찾지 못할 수 있음.

---

2. Open-Addressing 기술

선형 프로빙(Linear probing)

• 일반적인 해쉬 함수가 주어졌을때 보조 해쉬 함수(auxiliary hash function)를 사용해서 선형 프로빙을 하는 방식
  • h(k,i) = (h'(k)+i) mod m
• 선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈slot을 찾는 작업을 반복한다.

선형 프로빙의 장점과 단점

• 구현은 매우 쉬우나 primary clustering 문제가 있다.
• 값이 들어있는 slot의 수가 많으면 평균 검색시간이 증가한다.
• key값을 넣을 빈 slot은 뭉쳐 있는 slot들의 끝부분에 존재하기 때문에 값이 들어있는 slot들이 뭉쳐있는 경우가 많다.

이를 개선한것이 Quadratic Probing이다.

---

이차식 프로빙 (Quadratic Probing)

• 이차식 프로빙은 다음과 같은 형태의 해쉬 함수를 사용한다.
  • h(k,i) = (h'(k)+c1*i+c2*i^2) mod m
• 이때 h'는 보조 해쉬 함수이고, c1과 c2는 0이 아닌 상수
• 즉, 주어진 hash함수 외에 i에 대한 2차함수꼴로 slot을 이동하면서 빈 slot을 찾는다.

이차식 프로빙의 단점

• 만약 두 key의 처음 probe값이 동일하다면 빈 slot을 찾는 과정이 동일하므로 같은 slot을 탐색
• 이런 특성을 secondary clustering이라고 부른다.
•  

---

이중 해싱 (Double hashing)

• 이중 해싱은 다음과 같은 형태의 해쉬 함수를 사용한다.
  • h(k,i) = (h1(k)+i*h2(k)) mod m
• 처음 탐색하는 위치는 T[h1(k)]이다.
• 그 다음부터는 h2(k) mod m 많큼 이동하면서 탐색한다.
• 즉 충돌이 발생했을 때, 이동하는 거리가 hash 함수에 의해 계산되어 무작위로 빈 slot을 찾게한다.

이중 해싱의 주의점

• h2(k) 함수는 해쉬 테이블의 크기 m과 서로소 관계여야한다.
• 이것을 만족하는 가장 쉬운 방법은 m을 2의 지수승으로 두고 h2가 항상 홀수가 되도록 만드는 것이다.
• 다른 방법은 m을 소수로 하고 h2을 m보다 작은 양수로 정하는 것이다.

---