[10] Hash Table, 해시 테이블

✅ 해시 테이블이란

해시 테이블(Hash Table)은 키(Key)에 데이터(Value)를 저장하는 자료형이다.

파이썬에서 공부했던 딕셔너리와 비슷한 개념 정도가 아니라, 해시를 구현할 때 딕셔너리 타입을 사용하면 된다. 

해시 테이블은 키를 통해 데이터를 바로 찾을 수 있는 장점이 있는데 시간 복잡도가 O(1)으로 매우 빠르다. 

 

✅ 해시 주소란

해시 주소(Hash Address)는 해시 값이다. Key를 해싱 함수로 연산해서 나오는 값이 해시 값이다. 

 

✅ 해시 함수란

해시 함수(Hash Function)는 임의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수이다.

가장 간단한 형태는 데이터를 지정된 숫나로 나눈 뒤에 나머지를 인덱스로 사용하는 방법인데 코드로 나타내면 다음과 같다.

 

def HashFunction(key):
	return key%9

 

만약 해시 테이블에 key가 3인 값이 들어가 있는 상황에, key가 12인 데이터를 저장하려고 하면 나머지가 3으로 같기 때문에 충돌(Collision)이 일어난다. 이러한 충돌을 막는 방식은 체이닝 기법(Chaining)과 개방주소 기법(Open addressing)이 있다.

 

✅ 해시 테이블 기본 구현

해시 테이블에 (key, value)를 저장하는 방법은 다음과 같다.

 

1. key의 아스키(ASCII) 코드를 리턴한다 - 문자인 채로는 해싱함수가 계산을 못하잖하 [파이썬에서는 ord()를 사용]

2. 아스키 코드로 바뀐 key를 해싱함수에 넣어서 해시 주소(hash)를 알아낸다.

3. 해시 테이블의 해시 주소에 value를 넣는다.

 

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [0 for data in range(self.size)]
    
    def getKey(self, data):
        self.key=ord(data[0]) # ord() : 문자의 아스키(ASCII)코드 리턴
        return self.key
    
    def hashFunction(self, key):
        return key%self.size
    
    def getHash(self, key):
        findKey = self.getKey(key)
        return self.hashFunction(findKey)
    
    def add(self, key, value):
        hash = self.getHash(key)
        self.table[hash] = value
    
    def get(self, key):
        hash = self.getHash(key)
        return self.table[hash]

    def delete(self, key):
        hash = self.getHash(key)
        if self.table[hash] != 0:
            self.table[hash] =0
            return True
        else:
            return False

 

 

✅ 체이닝 기법(오픈 해싱)

 

체이닝 기법은 각 버킷(Bucket, 해시테이블의 각 원소)에 링크드 리스트(또는 이중리스트)를 생성하고 버킷이 링크드 리스트의 가장 앞 노드를 바라보게 하는 방법이다. 충돌이 발생했을 때 같은 버킷의 링크드 리스트에 마지막 노드로 값을 추가해주면 된다. 

 

✅ 이중 리스트로 구현

class HashChaining:
    def __init__(self, size):
        self.size = size
        self.table = [0 for data in range(self.size)]
    
    def getKey(self, data):
        self.key=ord(data[0]) # ord() : 문자의 아스키(ASCII)코드 리턴
        return self.key
    
    def hashFunction(self, key):
        return key%self.size
    
    def getHash(self, key):
        findKey = self.getKey(key)
        return self.hashFunction(findKey)
    
    def add(self, key, value):
        hash = self.getHash(key)
        
        if self.table[hash] == 0:
            self.table[hash] = [[key, hash]]
        else:
            for i in range(len(self.table[hash])):
                if self.table[hash][i][0] == key:
                    self.table[hash][i][1] = value
                    return
                self.table[hash].append([key, value])
    
    def get(self, key):
        hash = self.getHash(key)
        if self.table[hash] ==0:
            return False
        else:
            for i in range(len(self.table[hash])):
                if self.table[hash][i][0] == key:
                    return self.table[hash][i][0]
            return False

    def delete(self, key):
        hash = self.getHash(key)
        if self.table[hash] != 0:
            for i in range(len(self.table[hash])):
                if self.table[hash][i][0] == key:
                    if len(self.table[hash]) == 1:
                        self.table[hash] = 0
                    else:
                        del self.table[hash][i]
            return False
        else:
            return False

 

✅ 개방 주소법(폐쇄 해싱)

 

개방 주소법은 위 그림으로 보면 쉽게 알 수 있다. 위 그림의 해싱 함수는 key%7을 리턴해 해시 테이블의 인덱스로 사용한다. 데이터가 문제 없이 잘 들어가다가 맨 마지막 55를 삽입하고 싶을 때 나머지가 6이라서 충돌이 일어난다. 이 때, 당황하지 않고 테이블을 탐색하며 빈 자리에 들어가는 것이다.

 

 

✅ 구현

class HashChaining:
    def __init__(self, size):
        self.size = size
        self.table = [0 for data in range(self.size)]
    
    def getKey(self, data):
        self.key=ord(data[0]) # ord() : 문자의 아스키(ASCII)코드 리턴
        return self.key
    
    def hashFunction(self, key):
        return key%self.size
    
    def getHash(self, key):
        findKey = self.getKey(key)
        return self.hashFunction(findKey)
    
    def add(self, key, value):
        hash = self.getHash(key)
        
        if self.table[hash] == 0:
            self.table[hash] = [[key, hash]]
        else:
            for i in range(len(self.table[hash])):
                if self.table[hash][i] == 0:
                    self.table[hash][i] = [key, value]
                    return
                elif self.table[i][0] == key:
                    self.table[i] = [key, value]
                    return
    
    def get(self, key):
        hash = self.getHash(key)
        for i in range(hash, len(self.table)):
            if self.table[i][0] == key:
                return self.table[i][1]

    def delete(self, key):
        hash = self.getHash(key)
        
        for i in range(hash, len(self.table)):
            if self.table[i] == 0:
                continue
            if self.table[i][0] == key:
                self.table[i] = 0
                return

 

✅ 해시 테이블의 장점

데이터를 저장하고 읽는 속도라 빠르고, 데이터 중복 검사가 쉽다. 

 

✅ 해시 테이블의 단점

충돌이 일어날 경우, 이를 해결해 주어야 한다. (충돌이 안 일어나면 O(1), 일어나면 O(n)이기 때문)