[파이썬 자료구조] 해쉬테이블 구현해보기

파이썬에서는 딕셔너리로 이미 구현이 되어있는 해쉬테이블을 굳이 구현해보겠습니다. 개인적인 이해를 위한 글이니 재미있게(?) 봐주셨으면 합니다.

해쉬테이블(Hash table)

해쉬테이블은 키(Key)에 데이터(Value)를 저장하는 데이터 구조입니다. 나열의 구조인 스택이나 큐와는 다르게 Key를 통해 바로 데이터를 받아올 수 있습니다. 다루기 편하고 검색 속도가 엄청나게 빨라진다는 장점이 있습니다.

파이썬에서는 딕셔너리로 구현이 되어있고 다른 언어는 공간을 확보하고 해쉬테이블을 사용하지만 파이썬은 그럴 필요는 없습니다.

해쉬테이블은 Key-Value의 함수역할을 하는 해싱 함수를 통해 데이터를 반환하는 방식입니다. 즉, 해싱함수를 h라 할 때h(Key)=Value가 됩니다. 함수역할을 하긴 하지만 value가 중복되면 충돌이 일어나는 단점이 있습니다. 충돌의 의미는 서로 다른 두개의 입력값에 대해 동일한 출력값을 내는 상황을 의미합니다.

한개의 데이터를 저장할 수 있는 공간을 슬롯(slot)이라 하는데 Key에 해당하는 해쉬 값을 슬롯에서 가져옵니다.

해쉬테이블의 장점과 단점

앞서 얘기했지만 장단점을 정리하면 이렇습니다.

장점

1. 데이터 저장/읽기 속도가 빠르다
2. 키에 따른 데이터 확인이 쉬움

단점

1. 저장공간이 많이 필요
2. 여러 키에 해당하는 주소가 동일하면 충돌을 해결해야한다.

해쉬테이블 구현

간단한 예를 보이겠습니다.
해쉬테이블을 만들려면 먼저 해쉬테이블 공간을 만든 후
데이터를 넣고 빼는 역할을 하는 함수를 몇 개 만듭니다. 보통 해쉬키 대상은 숫자가 아니라 문자일 가능성이 높습니다. 그렇지만 해싱함수에는 숫자가 들어가야합니다. hash()함수를 쓰면 이런 문자를 숫자로 전환시킬 수 있습니다. 물론 해쉬키 기능을 할 수 있게 말이죠.

해쉬키 만들기

hash_table = list([0 for i in range(8)])

#해쉬키 만들기
def get_key(data):
    return hash(data)

get_key('Ann')

해싱 함수 만들기

해싱 함수도 만듭니다. 해싱함수는 다양하게 만들 수 있는데 나머지 값을 사용하는 Division법을 사용하겠습니다.

def hash_func(key):
        return key % 4

이제 값을 저장하고 저장한 값을 꺼내오는 기능만 추가하면 됩니다. 현재 해싱함수 기법은 hash()로 하면 충돌이 일어날 수 있으니 아스키 코드로 변환해 충돌을 방지한 후 진행하겠습니다.
아스키 코드 변환은 ord 함수로 할 수 있습니다.

data1 = 'Ann'
data2 = 'Red'
data3 = 'Hat'
print(ord(data1[0]),ord(data2[0]),ord(data3[0]))

나머지가 1, 2, 0 순으로 만들어졌습니다. 나머지로 나온 값이 인덱스가 되어서 hash_table 인덱스에 value값이 들어갈 것입니다.

값 저장하기

이제 값을 저장합니다. key-value 값으로 연결해주기만 하면 됩니다. hash_address로 해싱함수 정의를 한 후 연결합니다.

def save_data(data,value):
        key = ord(data[0])
        hash_address = hash_func(key)
        hash_table[hash_address] = value

save_data('Ann','01012345678')
save_data('Red','01023456789')
save_data('Hat','01034567891')

hash_table

만들어 놓은 hash_table에 출력하면 위에서 만든 해싱함수 방식으로 저장이 되는 것을 볼 수 있습니다.

구현 확인

마지막입니다. 실제로 key-value 로 읽어지는지 확인합니다.

def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

get_data('Ann')

Ann에 해당하는 value 값이 출력되었습니다.

 

마치며

지금은 구현에만 초점을 맞췄습니다. 해쉬테이블의 원리상 충돌은 불가피합니다. 

충돌에 대한 얘기는 다음 포스팅에 적어놓았습니다. 참고하시기 바랍니다.

 

[파이썬 자료구조] HashTable 충돌 시 적용 알고리즘

[파이썬 자료구조] HashTable 충돌 시 적용 알고리즘