[자료구조] 탐색 3. 해싱

지금까지 우리가 배운 탐색 방법은 모두 탐색키와 각 레코드의 킷값을 비교하여 원하는 레코드를 찾는 방식이었다.
그러나 해싱은 킷값에 산술적인 연산을 적용하여 레코드가 저장되어야 할 위치를 직접 계산하여 탐색하는 방식이다.

이 때 레코드가 저장될 위치를 계산하는 함수를 해시 함수(hash function)이라고 하며, 해시 함수에 의해 계산된 위치에 레코드를 저장한 테이블을 해시 테이블(hash table)이라고 한다. 해시 테이블은 M개의 버킷(bucket)이 담아져 있는데, 버킷이란 레코드를 담아두는 메모리를 뜻한다. (버킷은 여러 개의 슬롯으로 이루어져 있지만… 복잡하므로 버킷 1개에는 1개의 슬롯만 있다고 가정하자)

그런데 탐색 키의 개수가 엄청나게 많은 경우에는 해시 테이블의 크기가 엄청나게 커야만 한다. 모든 탐색 키를 다 저장할 수 있어야 하기 때문이다. 그런데 우리는 그렇게 큰 테이블을 만들기에는 메모리 낭비가 너무 심하다는 것을 잘 알고 있다. 해싱에서도 이를 해결하기 위해 해시 주소(hash address)를 사용하는데, 해시 함수를 통해 수많은 탐색 키들을 작은 정수로 대응시키는 것이다.

즉 정리하자면 킷값 key가 입력되면, 해시 함수로 연산한 결과인 해시 주소 h(key)에 key를 담은 버킷을 저장하는 것.

그런데 버킷의 수가 충분하지 않다면, 서로 다른 키가 해시 함수를 적용한 후 같은 해시 주소로 계산되는 상황이 발생하는데 이를 충돌(collision)이 일어났다고 한다.
일반적으로 충돌은 충돌이 일어난 주소의 다음 빈 공간에 킷값을 저장하는 방식을 통해 처리할 수 있으나, 만약 충돌이 버킷의 수보다 더 많이 발생하는 경우, 즉 오버플로(Overflow)가 일어난 경우에는 이를 반드시 해결해주어야 한다.

• 선형 조사에 의한 오버플로 처리
  해싱 함수로 계산된 버킷에 빈 슬롯이 없으면 그 다음 버킷에서 빈 슬롯이 있는지를 찾는 방법.
  테이블의 k번째 위치인 ht[k]에서 충돌이 발생했다면 다음 위치인 ht[k+1]부터 순서대로 비어 있는지를 살피고, 빈 공간이 있으면 저장한다.
  비어 있는 공간이 나올 때까지 계속되며, 만약 처음 충돌이 발생한 곳으로 다시 돌아왔다면 테이블이 가득 찬 상태이다.
  선형 조사법으로 오버플로를 처리하면 한 번 충돌이 발생한 위치 주변에 항목들이 집중되는 현상이 자주 일어나는데, 이를 군집화(clestering) 현상이라고 한다. 그도 그럴 게 충돌이 일어난 바로 다음 슬롯에 자리가 있으면 바로 저장하는 형태인지라…
  그래서 선형 조사법은 간단하게 처리할 수 있지만 군집화로 인해 오히려 탐색의 효율이 저하될 수도 있다.
• 체이닝에 의한 오버플로 처리
  버킷을 연결 리스트로 구현하여 하나의 버킷에 여러 개의 레코드를 저장할 수 있도록 하는 방법.
  체이닝은 해시 테이블을 연결 리스트로 구성하므로 필요한 만큼의 메모리만 사용하게 되어 공간적으로도 효율적이며, 오버플로가 발생한 경우 해당 버킷에 할당된 연결 리스트만 처리하게 되므로 시간적으로도 효율적이다.
  그래서 오버플로 처리는 체이닝으로 구현하는 것이 효율적이다!

해시함수

그렇다면 해시 함수는 어떤 방식으로 만드는 것이 좋을까?
좋은 해시 함수는 충돌이 적어야 하고, 주소가 테이블에서 고르게 분포되어야 하며, 계산이 빨라야 한다.
간단하면서도 적절한 해시 함수의 예시를 살펴보자.

• 제산 함수: 탐색키가 정수일 경우 나머지 연산 %을 이용하여 해시 주소를 계산한다.
• 폴딩 함수: 탐색키를 몇 개의 부분으로 나누어 이를 더하거나 비트별 XOR과 같은 부울 연산을 이용하여 해시 주소를 계산한다.
• 중간 제곱 함수: 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다.
• 비트 추출 방법: 해시 테이블의 크기가 M = 2k일 때 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용한다.
• 숫자 분석 방법: 각 위치마다 수의 특징을 미리 알고 있을 때(학번 등) 유용하다. 키의 각 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용한다.
• hash() 함수: 파이썬의 경우에는 해시 함수가 기본적으로 제공된다. 해시 함수를 만들어 낼 별다른 아이디어가 없다면 그냥 기본적으로 제공되는 해시 함수를 사용하는 것도 좋다.

체이닝의 응용) 해시 맵

체이닝은 연결 리스트를 이용하므로 노드가 필요한데, 노드의 데이터를 맵으로 사용하면서 좀 더 효율적인 탐색 알고리즘 맵을 구현할 수 있다.
즉 해시 맵의 노드는 ((키-값), 다음 노드의 주소)로 이루어진 것!

class HashChainMap: # 체이닝으로 구현한 맵
    def __init__(self, M):
        self.table = [None] * M
        self.M = M

    def hashFn(self, key):
        sum = 0
        for c in key:
            sum = sum + ord(c)
        return sum % self.M

    def insert(self, key, value):
        idx = self.hashFn(key)
        self.table[idx] = Node(Entry(key, value), self.table[idx])

    def search(self, key):
        idx = self.hashFn(key)
        node = self.table[idx]
        while node is not None:
            if node.data.key == key:
                return node.data
            node = node.link
        return None

    def delete(self, key):
        idx = self.hashFn(key)
        node = self.table[idx]
        before = None # 연결리스트니까 선행노드 알아야 삭제 가능
        while node is not None:
            if node.data.key == key:
                if before is None:
                    self.table[idx] = node.link # 이 경우 None이겠지?
                else:
                    before.link = node.link
                return
            else:
                before = node
                node = node.link

    def display(self, msg):
        print(msg)
        for idx in range(len(self.table)):
            node = self.table[idx]
            while node is not None:
                print("[%2d] -> " % idx, end="")
                while node is not None:
                    print(node.data, end=" -> ")
                    node = node.link
                print()

---

정리

해시 부분은 정말 어렵고 복잡해서… 내가 제대로 이해한 것인지도 모르겠다. 지금 글을 쓰면서 다시 공부하고 있는데도 여전히 헷갈리는 부분이 많다. 특히 버킷과 슬롯 이 부분은 너무 헷갈리는데 혹시 제가 틀리게 서술한 부분이 있다면 혹시 알려준다면 감사하겠습니다(__)

 

 

작성일자: 2023-03-12