알고리즘 - 해싱

해싱

• 순차 탐색이나 이진 탐색은 탐색 키와 각 레코드를 비교하여 원하는 레코드를 찾음
• 해싱은 탐색 키에 어떤 함수를 돌려 레코드가 저장되어야 할 위치를 바로 계산

해싱의 구조

• 해시 테이블: 레코드를 저장한 테이블
• 테이블은 M개의 버킷으로 이루어짐, 각 버킷은 보통 여러개의 슬롯으로 나누어짐
• 각 슬롯에 하나의 레코드가 저장된다

이상적인 해싱과 실제의 해싱

• 충돌(collision): 두개의 서로 다른 키가 해시 함수에 의해 같은 주소로 계산되는 상황
• 버킷에 여러 개의 슬롯이 있다면 비어 있는 다른 슬롯에 저장
• 오버플로(overflow): 충돌이 슬롯 수보다 더 많이 발생
• 이상적인 해싱: 충돌이 절대 일어나지 않는 경우
• 실제의 해싱: 충돌과 오버플로가 빈번하게 발생할 수 있음

해시 함수

• 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환 시켜주는 함수

(좋은 해시 함수의 조건)

• 충돌이 적게 발생해야 함
• 해시 결과가 테이블의 주소 영역 내에서 고르게 분포되어야 함
• 계산이 빨라야 함

제산 함수(나머지 연산 함수)

• $h(k) = kmodM$ (테이블의 크기: M, 탐색 키: k)
• 해싱에서 가장 흔히 사용, 항상 성능이 좋지만은 않음

탐색 키가 문자열인 경우

(문자열 탐색키에 대한 해시 함수 예)

def hashFnStr(key) :
    sum = 0
    for c in key : # 문자열의 모든 문자에 대해
        sum = sum + (ord(c))
    return sum % M

오버플로 처리하기

• 개방 주소법(open addressing): 오버플로가 일어나면 그 항목을 해시 테이블의 다른 위치(주소)에 저장 ex. 선형 조사법, 이차 조사법, 이중 해싱법 등
• 체이닝(chaining): 해시 테이블의 하나의 위치에 여러 개의 항목을 저장할 수 있도록 테이블의 구조를 변경

선형 조사법

• 개방 주소법 전략을 사용
• 조사(probing): 비어 있는 공간을 찾는 것

삽입 연산

• 군집화: 한번 충돌이 발생한 위치 부근에서 연속적으로 충돌이 발생하는 경향ㄷ

M = 13
table = [None]*M

def hashFn(key) :   # 해시 함수
    return key % M

def lp_insert(key) :
    id = hashFn(key)
    count = M
    while count>0 and (table[id] != None and table[id] != -1) :
#    while count>0 and (table[id] != None) :
        id = (id + 1 + M) % M   # 다음 위치로 이동
        count -= 1              # 검사할 남은 위치의 수

    if count > 0 :
        table[id] = key      # 해당 슬롯에 항목 저장
    return

탐색 연산

• 해당 키의 레코드를 찾거나, 레코드가 없는 버킷을 만나거나 모든 버킷을 다 검사할 때까지 진행

  def lp_search(key) :
    id = hashFn(key)
    count = M
    while count>0 :
        if table[id] == None :  # 찾는 항목이 테이블에 없음
           return None
        if table[id] != -1 and table[id] == key : 
  #        if table[id] == key : 
            return table[id]    # 찾는 항목이 테이블에 있음
        id = (id + 1 + M) % M   # 없으면 다음 위치 검사
        count -= 1
    return None
  

삭제 연산

• 빈 버킷을 두 가지로 분류해야 함
• 한번도 사용하지 않은 것, 삭제되어 현재 비어 있는 것
• 탐색 과정은 한 번도 사용이 안 된 버킷을 만나야만 중단 됨

def lp_delete(key) :
    id = hashFn(key)
    count = M
    while count>0 :
        if table[id] == None : return None
        if table[id] != -1 and table[id] == key : 
            table[id] = -1
            return
        id = (id + 1 + M) % M
        count -= 1

선형 조사법의 테스트 프로그램

print("   최초:", table )
lp_insert(45);  print( "45 삽입:", table )
lp_insert(27);  print( "27 삽입:", table )
lp_insert(88);  print( "88 삽입:", table )
lp_insert(9);   print( " 9 삽입:", table )

lp_insert(71);  print("71 삽입:", table )
lp_insert(60);  print("60 삽입:", table )
lp_insert(46);  print("46 삽입:", table )
lp_insert(38);  print("38 삽입:", table )
lp_insert(24);  print("24 삽입:", table )
lp_delete(60);  print("60 삭제:", table )
print("46 탐색:", lp_search(46) )

실행 결과

최초: [None, None, None, None, None, None, None, None, None, None, None, None, None]
45 삽입: [None, None, None, None, None, None, 45, None, None, None, None, None, None]
27 삽입: [None, 27, None, None, None, None, 45, None, None, None, None, None, None]  
88 삽입: [None, 27, None, None, None, None, 45, None, None, None, 88, None, None]
 9 삽입: [None, 27, None, None, None, None, 45, None, None, 9, 88, None, None]
71 삽입: [None, 27, None, None, None, None, 45, 71, None, 9, 88, None, None]
60 삽입: [None, 27, None, None, None, None, 45, 71, 60, 9, 88, None, None]
46 삽입: [None, 27, None, None, None, None, 45, 71, 60, 9, 88, 46, None]
38 삽입: [None, 27, None, None, None, None, 45, 71, 60, 9, 88, 46, 38]
24 삽입: [24, 27, None, None, None, None, 45, 71, 60, 9, 88, 46, 38]
60 삭제: [24, 27, None, None, None, None, 45, 71, -1, 9, 88, 46, 38]
46 탐색: 46

군집화 문제 완화 방법

• 해싱은 공간을 이용해 시간 복잡도를 $O(1)$ 까지 낮출 수 있는 최강의 탐색 기법
• 이차 조사법: 주소를 1씩 증가시키는 것이 아니라 $h(k), h(k)+1, h(k)+4, h(k)+9와 같이 제곱의 순으로 움직이는 방법
• 이중 해싱법 또는 재해싱: 충돌이 발생해 다음 위치를 정할 때, 원래 해시 함수와 다른 별개의 함수를 이용 탐색 키가 다르면 1차 해시 주소가 같아도 2차 함수에서 다른 주소가 나오고, 따라서 집중을 완화할 수 있는 아이디어