[자료구조💾] 11장 탐색과 해싱

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

11.1 순차 탐색

1) 탐색 (search)

- 주어진 레코드 집합에서 특정 키(key)와 일치하는 원소를 찾는 작업

- 키 필드 (key field) : 레코드의 여러가지 속성(attribute) 중 탐색 기준이 되는 속성

- 레코드들이 미리 정렬되어 있는 경우 탐색 효율이 높아진다.

- 탐색 알고리즘의 종류 : 순차 탐색, 이진 탐색, 보간 탐색, 해싱 탐색 등

 

2) 순차 탐색 (sequential search)

- 탐색 대상에 아무 조건이 없으며 탐색 키를 찾을 때까지 순차적으로 반복 비교하는 방법

- 원소들이 미리 정렬될 필요는 없지만 탐색 성능에 큰 편차가 발생한다.

- 시간 복잡도 : O(n)

- 코드

def seq_search(num, key, n):
  for i in range(n):
    if (num[i] == key):
      return i
  return -1

 

 

11.2 이진 탐색 (binary search)

- 이진 탐색 : 정렬된 대상 원소의 중간 값(median)과 탐색 키를 비교하는 방법

- 탐색할 대상 원소들을 미리 정렬해야 한다.

- 시간 복잡도 : O(log₂n)

- 알고리즘

1. 정렬된 원소 리스트에서 중간 값(median)의 위치를 계산한다.
2. 탐색 키와 중간 값을 비교하여 일치하면 위치를 반환하고 종료한다.
3. 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽 리스트로 탐색 범위를 변경하고, 중간값보다 크면 오른쪽 리스트로 변경한다.
4. 변경된 탐색 범위에 비교할 원소가 존재하면 과정 1번부터 반복한다.
5. 탐색 범위에 원소가 없으면 -1을 반환하고 탐색을 종료한다.

- 코드

def binary_search(num, key, left, right):
  while left <= right:
    mid = (left + right)//2
    if key == num[mid]:
      return mid
  return -1

 

 

11.3 보간 탐색 (interpolation search)

- 이진 탐색의 성능을 개선할 목적으로 개발된 알고리즘 → 탐색 범위에서 키 값의 차이와 위치(인덱스)의 차이가 비례한다는 가정을 바탕으로 한다.

- 탐색 키와 탐색 범위 경계의 차이를 고려하여 비교 위치를 결정한다.

pos = left + (right-left)*(key-list[left]) / (list[right]-list[left])

- 코드

def interpolate_search(num, key, left, right):
  while left <= right:
    if key < num[left] or key > num[right]:
      break

    pos = left + (key-num[left])*(right-left)//(num[right]-num[left])
    if key > num[pos]:
      left = pos + 1
    elif key < num[pos]:
      right = pos - 1
    else:
      return pos
  return -1

 

 

11.4 해싱 (Hashing)

1) 해싱 

- 탐색 키에 해시 함수를 적용하여 정보가 저장된 장소에 빠르게 접근할 수 있다.

- 이론적인 해싱의 탐색 속도 : O(1) → 대상의 수(n)에 상관없이 상수 시간(constant time)이 걸린다.

- 탐색할 명칭(x)에 해시 함수(hash function) f(x)를 적용하면 해시 코드가 반환되며 이를 통해 이 명칭의 정보가 저장된 해시 테이블(hash table)의 주소(b)를 획득할 수 있다.

 

2) 해시 테이블 (hash table)

- 명칭들이 저장되는 공간

- 버킷 (bucket) : 테이블의 행

- 슬롯 (slot) : 테이블의 열

- 코드 예시

class Hashing:
  def __init__(self, size, hf):
    self.size = size
    self.table = [None] * size
    self.collision = []
    self.hf = hf
  
  def hf1(self, key):
    return ord(key[0])-ord('a')
  
  def hf2(self, key):
    total = 0
    for s in key:
      total += ord(s)
    return total % self.size
  
  def add_table(self, sym):
    if self.hf == 1:
      bucket = self.hf1(sym)
    elif self.hf == 2:
      bucket = self.hf2(sym)

    if self.table[bucket] is None:
      self.table[bucket] = sym
    else:
      self.collision.append(sym)
  
  def show_table(self):
    print()
    i = 0
    for item in self.table:
      print("%2d" %i, item)
      i += 1

 

 

3) 명칭 밀도 (ID ; identifier density)

- 전체 명칭(T) 중 해시 테이블에 저장된 명칭 개수(n)의 비율

- ID = n / T

 

4) 적재 밀도 (LD ; loading density of factor)

- 해시 테이블 공간(b * s)에 대해 저장된 명칭 개수(n)의 비율

- LD = n / (b*s)

 

5) 동의어 (synonym)

- 해시 테이블에서 동일한 버켓 주소로 매핑된 서로 다른 명칭들

- f(i₁) = f(i₂)이면 i₁과 i₂는 동의어이다. (단, i₁ ≠ i₂)

 

6) 오버플로우 (overflow)

- 명칭 i가 이미 가득 찬 버켓(full bucket)으로 매핑되는 경우에 오버플로우가 발생한다.

 

7) 충돌 (collision)

- 서로 다른 명칭 i₁와 i₂가 해시 테이블의 같은 버켓으로 매핑되면 충돌이 발생한다.

- 버켓의 크기(버켓 당 슬롯 수)가 1개이면 충돌과 오버플로우가 동시에 발생한다.

 

8) 해시 함수

- 계산이 쉽고 명칭 간의 충돌을 최소화해야 한다.

- 균등 해시 함수 (uniform hash function)

• 임의의 명칭(x)에 적용했을 때 각 버켓에 적재될 확률(P)이 1/b인 함수
• P[f(x) = i] = 1/b, (0 ≤ i ≤ b-1)

- 중간 제곱 해시 함수 (mid-square)

• 명칭을 제곱한 결과 값의 일부를 해시 테이블 주소로 사용한다.
• 해시 테이블에 2r개의 버켓이 존재한다면 r개의 비트를 추출해서 사용
• f(10010100, 3) = 101 => 8개의 버켓

- 나눗셈 해시 함수

• 명칭을 특정 수로 나눈 나머지를 해시테이블 주소로 사용한다.
• f(x) = x % D
• 나누는 수 D를 짝수로 정할 경우 편중 분포 (skewed distribution)를 유발할 수 있으므로 소수나 홀수로 정하는 것이 좋다.

- 폴딩 해시 함수(folding) 

• 명칭을 해시 테이블 크기만큼 분할하여 합산한 결과를 주소값으로 사용한다.
• 이동 폴딩 (shift folding)
  • 명칭(x)를 k 자리로 분할한 뒤 순서대로 더하고 뒤의 k자리를 주소 값으로 사용한다.
  • k는 해시 테이블의 버켓 수에 비례하여 결정한다.
• 경계 폴딩 (boundary folding)
  • 분할한 세그먼트에서 짝수번째(두 번째, 네 번째) 부분을 뒤집어서 더한 후 이동 폴딩과 같이 뒤 k자리를 주소로 사용한다.

- 키 분석 해시함수 (digit analysis)

• 명칭의 내용을 알고 있는 경우 명칭에서 편중 분포를 유발할 수 있는 부분을 제거하고 주소로 사용할 부분만을 추출한다.

 

 

11.5 오버플로우 처리

1) 오버플로우

- 해시테이블에서 가득 찬 버켓에 다른 명칭이 매핑되는 현상

- 오버플로우 처리 (overflow handling)

• 오버플로우 현상을 처리하는 것
• 선형 조사법(linear probing), 2차 조사법(quadratic probing), 재해싱(rehashing), 해시 체인(hash chain) 등이 있다.

- 공개 주소법(open addressing)

• 명칭의 원래 버킷을 홈 버켓(home bucket)이라 하며 명칭을 홈 버켓이 아닌 다른 주소에 저장하는 방법
• 선형 조사법, 2차 조사법, 재해싱

 

2) 선형 조사법 (linear probing)

- 선형 조사법

• 특정 버켓에서 오버플로우가 발생하면 그 다음 비어 있는 버켓을 탐색하여 명칭을 추가하는 방법
• 빈 버켓이 찾을 때까지 해시 테이블을 순환하면서 순차 탐색한다.
• HT[(f(x)+j) % TABLE_SIZE], for 0 ≤ j < TABLE_SIZE

- 선형 조사법으로 탐색 시 발생할 수 있는 상황

• 탐색한 버켓이 이미 추가할 명칭(x)을 가지고 있는 경우 : 중복 명칭으로 오류 보고한다.
• 탐색한 버켓이 비어 있는 경우 : 버켓에 명칭을 삽입한다.
• 탐색한 버켓이 다른 명칭(y)을 포함하고 있는 경우 : 그 다음 빈 버켓을 계속 탐색한다.
• 홈 버켓(home bucket)으로 다시 돌아온 경우 : 전체 버켓이 모두 채워져 있는 해시 테이블 오버플로우 상태이며 오류를 보고한 후 종료한다.

- 문제점

• 명칭들이 서로 모이는 클러스터(cluster)를 형성한다.
• 충돌을 일으키는 명칭들이 바로 다음 빈 버켓에 저장되므로 충돌 횟수가 많을수록 버켓 비교 횟수가 증가한다.

- 클러스터 : 탐색 속도를 떨어뜨리는 원인이 되며 오버플로우 처리 시 클러스터를 최소화하는 것은 중요한 문제이다.

 

3) 개선된 오버플로우 처리

(1) 2차 조사법 (quadratic probing)

- 명칭 충돌이 발생할 때, 빈 버켓을 순차적으로 탐색하지 않고, 홈 버켓에서 제곱만큼 떨어져 있는 버켓을 조사한다.

- HT[(f(x) ± i²) % b] for 0 ≤ i ≤ (b-1)/2 (b는 버켓의 수)

 

(2) 재해싱 (rehasing)

- 오버플로우가 발생하면 다른 해시 함수를 사용하는 방법

- HT[f(x_i)] for i = 1, 2, ..., b

 

(3) 해시 체인 (hash chain)

- 해시 테이블의 각 버켓을 연결 리스트로 구현한다.

- 특정 버켓에서 충돌하는 모든 명칭들을 해당 버켓의 연결리스트에 추가하여 관리한다.

- 구조적으로 오버플로우가 발생하지 않는다.

- 버켓 수만큼의 연결 리스트가 필요하며, 연결 리스트가 길어질수록 추가적인 순차탐색 시간(O(n))이 필요하다.