자료구조 Ch 6. Hash Table (해시 테이블)

프로그래밍 공부

자료구조 Ch 6. Hash Table (해시 테이블)

응_비 2021. 5. 20. 13:08

해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

해싱 : 데이터의 신속한 탐색을 위해 데이터를 해싱 테이블 이라는 배열에 저장하고, 데이터의 키 값을 주면 이를 적절한 해싱함수를 통해서 테이블의 주소로 변환하여, 원하는 데이터를 찾아내는 방법.

- 속도는 가장 빠르지만, 충돌현상 시 오버플로우 해결의 부담이 과중되며, 많은 기억공간을 요구하는 검색방법.

이진탐색트리에서 최대성능은 O(log n) 이었다.
만약, 데이터의 키로 1차원 배열의 인덱스를 사용하면 O(1)도 가능하다.
이는 공간으로 시간을 사는 개념이다.

문제는 배열의 공백이 많아 메모리 낭비가 심하다.
다른 방법으로 키를 직접 쓰지 말고, 키를 특정함수(예: 나머지 함수)에 넣고 결과를 인덱스로 사용해 공백을 줄이는 방법을 사용할 수 있다.

이 경우, 메모리 낭비는 줄일 수 있지만, 서로 다른 키들이 동일한 해시값을 가질 때 충돌문제가 발생한다.
가장 이상적인 해시함수는 키들을 균등하게(Uniformly) 해시테이블의 인덱스로 변환하는 함수다.
널리 사용되는 해시함수는 나눗셈(Division) 함수다. 나눗셈 함수는 키를 M으로 나눈 뒤, 그 나머지를 해시값으로 사용한다.
h(key) = key % M이고, 따라서 해시테이블의 인덱스는 0에서 M-1이 됨
M은 일반적으로 key 개수의 3배 정도이며 소수(prime number)를 사용한다.

충돌 처리

충돌이 일어날 경우, 처리하는 방법으로 개방주소방식과 폐쇄 주소방식이 있다.
개방 주소방식과 폐쇄 주소방식의 차이는 충돌이 일어날 경우,
충돌지점에서 다른 주소까지 개방해서 원소를 삽입할 수 있는 경우가 개방주소방식이고,
폐쇄주소방식은 충돌이 일어난 주소에서 문제를 해결하는 방식이다.

개방주소방식

개방주소방식은 충돌이 일어난 위치 다음 인덱스로 이동하면서 처음나오는 빈 주소에 저장하는 방식이다.
-> 개방주소방식 : 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사하여 총돌된 데이터를 입력하는 방식.
-> 해싱에서 오버플로우를 해결하는 기법으로, 레코드가 초과되면 주소를 다시 계산하여 저장하는 방법.
메모리의 크기가 M개이므로 (h(key)+j) % M 으로 위치를 이동한다. 즉, M번째까지 가면 다시 0번째가 됨을 의미한다.
x = [25, 37, 18, 55, 22, 35, 50, 63]을 해시 테이블에 저장해보자.
- Linear Probing: 충돌시, 해당 인덱스에서 빈곳을 찾아 순차적으로 이동하다가 빈곳이 나오면 입력한다. (h(key)+j) % M
- Quad Probing: 충돌시, 해당 인덱스에서 빈곳을 찾을 때, 순차적으로 이동하는 것이 아니고 점프간격을 제곱으로 이동하여 삽입여부를 결정한다. (h(key)+j**2) % M
- Random Probing: 충돌시, 해당 인덱스에서 빈곳을 찾을 때, 그 다음 위치를 랜덤하게 이동하여 삽입 여부를 결정한다.
  단, 탐색을 위해서는 난수의 seed를 지정해야 한다. (h(key)+randInt) % M
  seed를 시간으로 줄 경우, 찾을 수 없으므로 반드시 일정한 seed를 줘야 한다.
- Linear Probing의 경우, 인덱스가 한쪽으로 뭉치는 현상이 발생하는데 이를 방지하고자 Quad, Random 등의 방법을 사용한다.
- Quad Probing의 경우에는 다른쪽에서 뭉침현상이 나타나고 Random Probing은 무작위 위치에서 뭉침현상이 발생한다.
Linear Probing 설명

아래 코드는 Linear Probing 을 구현한 것이다.

class Hash_Linear:
    def __init__(self,m):
        self.m = m
        self.h = [None] * m

    def insert(self, key, item):
        if self.is_full() == True:
            print("Hash Full~~~")
        else:
            idx = key % self.m
            if self.h[idx] == None:
                self.h[idx] = [key,item]
            else:
                for j in range(1, self.m+1):
                    nextIdx = (idx + j) % self.m
                    if self.h[nextIdx] == None:
                        self.h[nextIdx] = [key,item]
                        break

    def is_full(self):
        if None in self.h:
            return False
        else:
            return True

    def get(self, key):
        idx = key % self.m
        if self.h[idx][0] == key:
            return self.h[idx][1]
        else:
            j = 1
            while True:
                nextIdx = (idx + j) % self.m
                if self.h[nextIdx][0] == key:
                    return self.h[nextIdx][1]
                else:
                    j += 1

x = [25, 37, 18, 55, 22, 35, 50, 63, 95, 32, 1, 13, 17]

h = Hash_Linear(13)
for val in x:
    h.insert(val, 'a'+str(val))

for val in x:
    print(val, h.get(val))

h.insert(98, 'a'+str(98))

폐쇄주소방식

충돌이 일어날 경우, 다른 메모리에 저장하는 것이 아니고 그 메모리 안에서 해결하는 방법이다.
-> 폐쇄 주소법 : 오버플로 발생 시 이를 별도의 기억공간에 두고 링크를 연결하여 사용하는 방법
대표적 해결방법으로 Chaining을 사용한다.
-> 체이닝 : 충돌이 발생하면 각 데이터를 해당주소에 있는 연결리스트에 삽입하여 문제를 해결하는 방법

체이닝은 아래 그림처럼 메모리에 Linked List 객체를 삽입해서 중복될 경우, 리스트를 순차탐색하는 방법을 사용한다.

class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.link = None

# LinkedList Class: Linked List에 노드를 추가(append)하고 노드를 찾는(get) 메소드가 있다.
class LinkedList:
    def __init__(self):
        self.root = Node()
    # 리스트 마지막에 노드를 삽입한다.
    def append(self, key, value):
        # 추가할 새 노드를 만든다.
        newNode = Node(key, value)
        # 현위치를 루트로 지정하고 노드를 추가한다.
        curNode = self.root
        cnt = 0
        # 현 위치가 비어 있으면 현 위치에 삽입
        if curNode.key == None:
            self.root = newNode
        # 현 위치가 비어 있지 않으면 다음 노드로 옮기는 작업을 마지막 노드가 나타날 때 까지 반복한다.
        # 마지막 노드를 만나면 마지막 노드 다음에 새 노드를 삽입한다.
        else:
            while curNode.link != None:
                cnt += 1
                curNode = curNode.link
            curNode.link = newNode
        return cnt

    def get(self, key):
        curNode = self.root
        cnt = 0
        if curNode.key == key:
            return curNode.value, cnt
        else:
            while curNode.link != None:
                curNode = curNode.link
                cnt += 1
                if curNode.key == key:
                    return curNode.value, cnt
            return None


class ChainHash:
    def __init__(self, n):
        # 데이터 수의 3배를 기준으로 소수 리턴한다.
        self.m = self._getPrime(3 * n)
        self.h = [None] * self.m

    def _getPrime(self, n):
        # 1~n 사이의 소수를 구하고 가장 큰 두 개의 소수를 리턴한다.
        import numpy as np
        is_prime = np.array(list(range(n+1)))
        N_max = int(np.sqrt(len(is_prime) - 1)) # looping 2 to sqrt(n)

        for j in range(2, N_max + 1):
            is_prime[2*j::j] = 0
        is_prime = np.setdiff1d(is_prime,np.array([0,1])) # is_prime - [0,1]
        return is_prime[-1]

    def insert(self, key, item):
        idx = key % self.m
        # 구한 주소가 비어 있으면 해당 주소에 빈 리스트를 만들고 새노드를 추가한다.
        if self.h[idx] == None:
            self.h[idx] = LinkedList()
            self.h[idx].append(key, item)
        else:
        # 구한 주소가 비어 있지 않으면 해당 주소 리스트 루트부터 끝으로 이동하여 마지막 노드 링크에 새 노드를 추가한다.
            #print(key, "충돌")
            curNode = self.h[idx].root
            while curNode.link != None:
                curNode = curNode.link
            curNode.link = Node(key, item)

    def get(self, key):
        idx = key % self.m
        xList = self.h[idx]

        return xList.get(key)


x = [25, 37, 18, 55, 22, 35, 50, 63]

h = ChainHash(8)

for val in x:
    h.insert(val, 'a'+str(val))

y = [26, 38, 19, 56, 23, 36, 51, 64]
for val in y:
    h.insert(val, 'a'+str(val))

print(h.get(26))