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

해시 테이블은 언어에 따라 해시맵, 사전 등으로 부른다. 해시 테이블은 key(키), value(값)으로 구성된 자료구조이다.

해시 함수란, 키를 매개변수로 사용하여 해시 테이블의 고유한 값을 반환하는 함수이다.

키를 해시함수에 넣으면 나오는 고유한 값을 인덱스로 사용하여 테이블에 값을 저장하거나 검색한다.

해시 테이블 기본 원리

key	value
"a"	"apple"
"b"	"banana"
"c"	"cherry"

위와 같이 키와 값이 있을 때, 해시 테이블에 저장하는 방법을 알아보자.

해시함수는 아스키코드를 테이블의 크기(3)로 나눈 나머지를 구하는 함수이다.

"a" 를 해시함수에 넣으면 -> hashFn(97 % 3) -> 1
"b" 를 해시함수에 넣으면 -> hashFn(98 % 3) -> 2
"c" 를 해시함수에 넣으면 -> hashFn(99 % 3) -> 0

따라서 아래 그림처럼 해시 테이블에 자료가 저장된다.

특징

key가 달라도 해시 값이 같을 때가 있는데, 이를 충돌이라고 한다. 충돌을 해결한느 방법은 2가지이다.

분리 연결법(Seperate Chaining): 충돌한 키의 자료를 연결 리스트로 저장
개방 주소법(Open Addressing): 충돌할 때 다음 빈자리를 찾아 자료를 저장

파이썬은 개방 주소법을 사용한다.

장점

자료 검색, 읽기, 저장 속도가 빠르다.
자료의 중복을 확인하기 쉽다.

단점

저장 공간이 더 필요하다.
충돌을 해결할 방법이 필요하다.

해시 테이블 클래스 만들기

class Hash_table:
    def __init__(self,length = 5):
        self.max_len = length
        self.table = [[] for _ in range(self.max_len)]

    def hash(self,key):
        res = sum([ord(s) for s in key])
        return res % self.max_len

    def set(self,key,value):
        index = self.hash(key)
        self.table[index].append((key,value))

    def get(self,key):
        index = self.hash(key)
        value = self.table[index]
        if not value:
            return None
        for v in value:
            if v[0] == key:
                return v[1]
        return None

if __name__ == '__main__':
    capital = Hash_table()
    country = ["Korea","America","China","England","Japan"]
    city = ["Seoul", "Washington", "Beijing", "London", "Tokyo"]
    for co, ci in zip(country, city):
        capital.set(co, ci)

    print("해시 테이블의 상태")
    print("===============")
    for i, v in enumerate(capital.table):
        print(i, v)
    print()
    print("해시 테이블의 검색 결과")
    print("====================")
    print(f"Capital of America = {capital.get('America')}")
    print(f"Capital of Korea = {capital.get('Korea')}")
    print(f"Capital of England = {capital.get('England')}")
    print(f"Capital of China = {capital.get('China')}")
    print(f"Capital of Japan = {capital.get('Japan')}")
    print(f"Capital of Brazil = {capital.get('Brazil')}")

__init__ 메서드: 해시 테이블의 크기 설정하고 빈 리스트를 만든다.
hash 메서드: 키를 문자열로 바꿔서 각 문자의 아스키코드를 더한 후 해시 테이블의 크기로 나눈 나머지를 구한다.
set 메서드: 키와 값을 받는다. 키를 해시함수에 넣어서 해시 값을 얻는다. => 해시 테이블에 키, 값을 추가한다.
get 메서드: 해시 테이블에서 키를 검색하여 값을 반환한다.

실행결과

해시 테이블의 상태
===============
0 [('America', 'Washington')]
1 []
2 [('England', 'London')]
3 [('Korea', 'Seoul'), ('China', 'Beijing')]
4 [('Türkiye', 'Ankara')]

해시 테이블의 검색 결과
====================
Captial of America = Washington
Captial of Korea = Seoul
Captial of England = London
Captial of China = Beijing
Captial of Japan = Tokyo
Capital of Brazil = None

실행결과를 보면 "Korea", "China"의 해시값이 모두 3이여서 같은 인덱스에 들어와 있다.
파이썬에서 해시함수가 필요하면 내장함수 hash를 이용한다.