C언어 기초/자료구조/C로 배우는 쉬운 자료구조/Chapter10 검색_2

반응형

 

C언어 기초/자료구조/C로 배우는 쉬운 자료구조/Chapter10 검색_1

---

계산 검색

---

4. 해싱

 1. 해싱이란?

• 해싱 Hahing 은 산술적인 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 계산의 검색 방식!
• 해시 함수 Hash Funtion: 키값을 원소 위치로 변환하는 함수
• 해시 테이블 Hash Table: 해시 함수로 계산된 주소 위치에 항목을 저장한 표

키값 → 해싱함수 → 해시주소(버킷주소) → 해시테이블

(해시테이블)

• 해시 테이블은 버킷 n개와 슬롯 m개로 구성
• 버킷 주소: 해시 함수에 의해 계산된 주소( 해시 함수는 0과 n-1사이의 버킷 주소만 만들어야 한다)
• 슬롯이 여러 개 있는 경우 순차 검색을 이용하여 해당 슬롯을 검색!
• 해시 테이블로 바로 이동하여 찾는 항목이 있으면 성공! 없으면 실패!
•  

---

해싱 용어 사전

• 동거자 Synonym: 서로 다른 키값을 가지지만 해시 함수에 의해 같은 버킷에 저장된 키값
• 충돌 Collision: 동거자가 생기는 현상
•  포화 버킷 상태: 버킷에 비어있는 슬롯이 없는 상태
                             → 포화 버킷 상태에서 충돌이 발생하면 오버플로!
• 키값 밀도 = 실제 사용중인 키값의 개수 / 사용 가능한 키값의 개수(들어올 수 있는 키값의 개수) → 키값 기준
• 적재 밀도 = 실제 사용 중인 키값의 개수 / 해시  테이블에 저장 가능한 전체 키값의 개수
                   = 실제 사용 중인 키값의 개수 / (버킷 개수 * 슬롯 개수) → 방 기준

---

 2. 해시 함수

   해싱 검색에서 가장 중요한 것은 키값의 위치를 계산하는 해시 함수!

• 해시 함수는 계산이 쉬워야 한다!
• 해시 함수는 충돌이 적어야 한다!
• 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다!

    해시 함수에는 중간 제곱 함수, 제산 함수, 승산 함수, 접지 함수, 숫자 분석 함수, 진법 변환 함수, 비트 추출 함수 등이 있다!

---

1) 중간 제곱 함수

 

 제곱! 작은 수를 만들지 않겠다! 하고 선언한 해시 함수이다.

중간 제곱 함수는 키값을 제곱한 결괏값에서 중간에 있는 적당한 비트를 주소로 사용!

 

---

▶예시

00110101 10100111 * 00110101 10100111 = 000010110011 1110100100101111001

• 제곱 결괏값에서 주소로 사용하는 비트 수는 해시 테이블의 버킷 개수에 따라 결정
• 버킷이 256개 있다면 버킷 주소는 0~255인 256개 값을 사용!
• 256개 값을 만들기 위해 필요한 최소 비트수는 8비트 이므로 제곱 결괏값에서 8비트를 주소로 사용한다.
•  

---

2) 제산 함수

 

 제산 Division 함수는 나머지 연산자 mod(C에서는 % 연산자)를 사용하는 방법!

• 카값 k를 해시 테이블 크기인 M으로 나눈 나머지를 해시 주소로 사용
• M으로 나눈 나머지 값의 범위는 0~(M-1)이므로 해시 테이블의 인덱스로 사용할 수 있다!
• 해시 테이블 크기 M은 적당한 크기의 소수 Prime Number을 이용

h(k) = k mod M

 

---

 

3) 승산 함수

 

 승산 함수는 곱하기 연산을 사용하는 방법!

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

 

---

 

4) 접지 함수

 접지 함수는 주로 키의 비트 수 > 해시 테이블 인덱스의 비트 수 일 때 사용

 

• 키값 k 가 있을 때 해시 테이블 인덱스의 비트 수와 같은 크기로 분할 → 분할된 부분을 모두 더하기

---

    1.이동 접지 함수

         이동 접지 함수는 각 분할 부분을 이동시켜서 오른쪽 끝자리가 일치하도록 맞춘 뒤 더함.

▶예시

12312312312인 경우

k₁ = 123

k₂ = 123

k₃ = 123

k₄ = 12

k₁+k₂+k₃+k₄ = 381 

---

    2. 경계 접지 함수

         경계 접지 함수는 분할된 각 경계를 기준으로 접으면서 서로 마주보도록 배치하고 더함.

▶예시

12312312312인 경우

k₁ = 123

k₂  = 321

k₃ = 123

k₄ = 21

k₁+k₂+k₃+k₄ = 588 

---

 

5) 숫자 분석 함수

• 숫자 분석 함수는 키값을 이루고 있는 각 자릿수의 분포를 분석하여 해시 주소로 사용

---

 

6) 진법 변환 함수

• 진법 변환 함수는 키값이 10진수가 아닌 다른 진수일 때 10진수로 변환
• 해시 테이블 주소로 필요한 자릿수만큼만 하위 자릿수만큼만 하위 자리의 수를 사용

---

 

7) 비트 추출 함수

• 비트 추출 함수는 해시 테이블의 크기가 2^k일 때
• 키값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 주소로 사용
• 충돌 발생 가능성이 많으므로 테이블 일부에 주소가 편중되지 않도록 키값의 비트를 미리 분석하여 사용

---

 3. 해싱에서 오버플로를 처리하는 방법

  1. 선형 개방 주소법

• 선형 조사법 Linear Probing
• 빈 슬롯이 없어 오버플로가 발생하면 그 다음 버킷에 빈 슬롯이 있는지 조사
• 빈 슬롯이 있으면 키값을 저장, 빈 슬롯이 없으면 다시 그 다음 버킷을 조사

 

  2. 체이닝

• 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키값을 저장할 수 있도록 하는 방법
• 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해 연결 리스트를 사용
• 각 버킷에 대한 헤드 노드는 1차원 배열, 슬롯은 헤드 노드에 연결 리스트 형태로 연결됨.