[자료구조] 해쉬 테이블 with Python

💡 해쉬 테이블?

: 해시테이블은 키에 대한 데이터를 저장하는 데이터구조이다.

: 키를 해시함수로 연산하여 해시 값을 알아내고, 이를 기반으로 키에 대한 데이터값을 알아낼 수 있다.

: 즉, 키를 통해 데이터를 바로 알아낼 수 있어 속도가 획기적으로 빨라진다.

: 파이썬의 딕셔너리 타입이 바로 해시테이블구조로 구현 되어있다.

 

💡 해쉬 테이블 구현하기

class Dict:
    def __init__(self):
        self.items = [None] * 8

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index] = value

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index]

my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test"))  # 3이 반환

 

💡 해쉬 테이블의 특징

[ 장점 ]

1) 키를 통해 데이터를 바로 알아낼 수 있어 저장/읽기 속도가 굉장히 빨라진다.

   -> 배열의 경우에는 모든 요소들을 하나씩 탐색해야한다.

2) 해시는 키에 대한 데이터가 있는지 확인이 쉬움(중복 체크)

 

[ 단점 ]

1) 저장 공간이 많이 필요하다.

    -> 공간과 탐색시간을 맞바꾸는 기법이다.

2) 데이터 공간을 작게 잡으면 충돌이 발생할 수 있다.

   -> 키에 해당하는 주소가 동일할 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요하다.

   -> 하단의 해시테이블의 충돌 해결 참고

 

[ 주요 용도 ]

1) 검색이 많이 필요한 경우

2) 저장/삭제/읽기가 빈번한 경우

3) 캐쉬 구현시(중복 체크가 빠르게 가능하기 때문)

 

💡 해시 테이블의 충돌 해결

1) Open hashing(개방 해시)

: 충돌이 발생한 데이터에 대해서는 해시테이블 밖에 추가적인 데이터공간에 저장하는 방법이다.

open hashing의 대표적인 예는 channing기법이 있다.

channing 기법에서는 충돌이 일어나면 linked list를 이용해서 뒤에 연결시켜 저장한다.

이때 얼만큼 충돌이 일어날지를 몰라서 배열이 아닌 linked list를 쓴다.

2) Linear Probing(폐쇄 해시)

: 해시 테이블의 빈 공간에 저장하는 방법이다.

: hash address의 다음부터 맨 처음 나오는 빈공간에 저장한다.

: 저장공간 활용도를 높일 수 있다는 장점이 있다.

 

💡 해시 테이블의 시간복잡도

1) 일반적인 경우 O(1)

2) 최악의 경우(충돌이 모두 일어나는 경우) O(n)

 

하지만 해시 테이블의 경우 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)이라고 할 수 있다.