해시 테이블

해시 테이블은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다. 해시 테이블의 시간 복잡도는 O(1)이다.

키와 값을 해시 테이블에 넣을 때 거치는 과정

키의 해시 코드를 계산
해시 코드를 이용하여 배열의 인덱스를 구함
배열의 각 인덱스에 키와 값으로 이루어진 연결 리스트가 존재

해시 함수의 두가지 성질

입력 원소가 해시 테이블 전체에 고루 저장되어 있어야 함
계산이 간단해야 함
⭐️ 첫번째 성질이 중요: 이 성질을 잘 만족해야 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 작아짐

해시 함수를 만드는 두 가지 방법

나누기 방법 : 해시 테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 수축시킴
h(x) = x mod m
⭐️ 여기서 m은 테이블의 크기, 소수여야 함
곱하기 방법 : 입력값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이블 크기를 곱해서 0부터 m-1 사이로 팽창 시킴
h(x) = ⎣m(xA mod 1)⎦
⭐️ 나누기 방법과 다르게 해시 테이블 크기 m을 아무렇게나 잡아도 상관없지만 컴퓨터의 이진수 환경에 맞게 $2^p$로 잡는 것이 자연스러움
💡상수 A를 어떻게 잡느냐에 따라 해시 값 분포가 많은 영향을 받는데 크누스는 잘 작동하는 A값으로 $\frac{\sqrt{5}-1}{2}$를 제안함

충돌 해결 두 가지 방법

오픈 해싱 (chaining)
같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아 관리
클로즈 해싱 (Open Addressing)
오픈 해싱처럼 추가 공간을 허용하지 않음, 모든 원소가 반드시 자신의 해시 값과 일치하는 주소에 저장된다는 보장이 없음, 정해진 규칙에 따라 다음 자리를 찾는데 를 찾는데 빈자리를 찾을 때까지 계속 찾음

클로즈 해싱에서 주소를 결정하는 대표적인 세 가지 방법

선형 조사
$h_j(x) = (h(x) + i)$ mod $m$
충돌이 일어난 자리에서 i에 관한 일차 함수의 보폭으로 점프를 함
🐱 특정 영역에 원소가 몰릴 때 치명적으로 성능이 떨어짐
이차원 조사
$h_1(x) = (h(x)+c_1i^2 + c_2i)$ mod $m$
$i = 0, 1, 2...$
선형 조사와 달리 이차 함수의 보폭으로 점프를 함
🐶 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있음
🐱 여러 개의 원소가 동일한 초기 해시 함숫값을 갖게 되면 모든 같은 순서로 조사할 수밖에 없어서 비효율적임
더블 해싱
$h_i(x)=(h(x)+i*f(x))$ mod $m$
다른 해시 함수 두 개를 사용한다.
🐶 두 원소의 첫 번째 해시 값이 같더라도 두 번째 함 수 값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프함

파이썬으로 해시 테이블 구현하기

파이썬으로 해시를 사용하려면 딕셔너리를 사용하면 되지만 직접 구현해보자

class HashTable:
    def __init__(self, table_size):
        self.table_size = table_size
        self.hash_table = [0 for _ in range(self.table_size)]

    def getKey(self, data):
        return ord(data[0])

    def hashFunction(self, key):
        return key % self.table_size

    def getAddress(self, key):
        hash_key = key if type(key) is int else self.getKey(key)
        hash_address = self.hashFunction(hash_key)
        return hash_address

    def put(self, key, value):
        hash_address = self.getAddress(key)
        self.hash_table[hash_address] = value

    def get(self, key):
        hash_address = self.getAddress(key)
        return self.hash_table[hash_address]

    def delete(self, key):
        hash_address = self.getAddress(key)
        if self.hash_table[hash_address] != 0:
            self.hash_table[hash_address] = 0
            return True
        else: return False

파이썬으로 오픈 해싱을 사용하는 해시 테이블 구현하기

class OpenHashTable:
    def __init__(self, table_size):
        self.table_size = table_size
        self.hash_table = [[] for _ in range(self.table_size)]

    def getKey(self, data):
        return ord(data[0])

    def hashFunction(self, key):
        return key % self.table_size

    def getAddress(self, key):
        hash_key = key if type(key) is int else self.getKey(key)
        hash_address = self.hashFunction(hash_key)
        return hash_address

    def put(self, key, value):
        hash_address = self.getAddress(key)

        if self.hash_table[hash_address]:
            for chaining_index in range(len(self.hash_table[hash_address])):
                if self.hash_table[hash_address][chaining_index][0] == key:
                    self.hash_table[hash_address][chaining_index][1] = value
                    return
            self.hash_table[hash_address].append([key, value])
        else:
            self.hash_table[hash_address] = [[key, value]]

    def get(self, key):
        hash_address = self.getAddress(key)

        if self.hash_table[hash_address]:
            for chaining_index in range(len(self.hash_table[hash_address])):
                if self.hash_table[hash_address][chaining_index][0] == key:
                    return self.hash_table[hash_address][chaining_index][0]
            return False
        else:
            return False

    def delete(self, key):
        hash_address = self.getAddress(key)

        if self.hash_table[hash_address]:
            for chaining_index in range(len(self.hash_table[hash_address])):
                if self.hash_table[hash_address][chaining_index][0] == key:
                    if len(self.hash_table[hash_address]) == 1:
                        self.hash_table[hash_address] = []
                    else:
                        del self.hash_table[hash_address][chaining_index]
                    return
            return False
        else:
            return False

파이썬으로 클로즈 해싱(더블 해싱)을 사용하는 해시 테이블 구현하기

class CloseHashTable:
    def __init__(self, table_size, parameter):
        self.table_size = table_size
        self.function_parameter = parameter
        self.hash_table = [[] for _ in range(self.table_size)]

    def getKey(self, data):
        return ord(data[0])

    def hashFunction(self, key):
        return key % self.table_size

    def hashFunction2(self, key):
        return 1 + key % self.function_parameter

    def getAddress(self, key):
        hash_key = key if type(key) is int else self.getKey(key)
        hash_address = self.hashFunction(hash_key)
        return hash_address

    def put(self, key, value):
        hash_address = self.getAddress(key)
        function2_return = self.hashFunction2(key)
        while self.hash_table[hash_address] and self.hash_table[hash_address][0] != "delete":
            hash_address = self.hashFunction(hash_address+function2_return)
        print(key, hash_address)
        self.hash_table[hash_address] = [key, value]

    def get(self, key):
        hash_address = self.getAddress(key)
        function2_return = self.hashFunction2(key)
        while self.hash_table[hash_address]:
            if self.hash_table[hash_address][0] == key: return self.hash_table[hash_address][1]
            hash_address = self.hashFunction(hash_address + function2_return)
        return False

    def delete(self, key):
        hash_address = self.getAddress(key)
        function2_return = self.hashFunction2(key)
        while self.hash_table[hash_address]:
            if self.hash_table[hash_address][0] == key: 
            	self.hash_table[hash_address] = ["delete", "delete"]
            hash_address = self.hashFunction(hash_address + function2_return)
        return False

💖 참고 자료 💖

[python] 자료구조 - 해시 테이블(Hash Table)

해시 테이블(Hash Table) 해쉬 테이블은 키와 밸류를 기반으로 데이터를 저장한다. 파이썬에서는 딕셔너리가 있어서 굳이 만들 필요는 없는데, 아무래도 파이썬으로 코드를 짜면 간단해서 파악하

jinyes-tistory.tistory.com

게일 라크만 맥도웰, [코딩 인터뷰 완전 분석], 프로그래밍 인사이트(2017)

문병로, [쉽게 배우는 알고리즘], 한빛 아카데미(2018)

저작자표시 비영리 변경금지