해쉬 테이블

 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

 

 해쉬 자료구조는 파이썬에서 딕셔너리와 같다. key값으로 빠르게 해당하는 value를 찾고 저장할 수 있는 자료구조이다. key와 매핑된 벨류를 반환하기 때문에 모든 배열을 돌아보지 않고 조회가 가능하므로 상수 시간의 시간 복잡도를 갖고 있다.

 

 알고리즘 문제를 풀다보면 시간 복잡도를 줄이기 위해 index()라는 함수보다 딕셔너리로 값들을 저장하곤 한다. 하지만 딕셔너리도 다소 메모리가 더 잡히는 부분 때문에 이러한 부분도 상황에 따라 개발자가 선택해야한다.

 

 간단한 해쉬 구현

# hash 함수를 활용한 딕셔너리 구현
class Dict():
    def __init__(self) -> None:
        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]

test_dict = Dict()
test_dict.put("test", 1)
print(test_dict.get('test'))

 위 코드는 완벽한 해쉬라고 볼 수 없다. 해쉬함수를 활용하여 인덱스를 정할 수 있지만, 인덱스 중복은 면치 못한다는 단점이 있다. 이러한 부분을 보완하기 위해 우리는 값들을 추가할 때 애초에 배열 안에 추가하는 방식으로 인덱스가 중복이 되어도 해당 배열에 마지막에 추가되는 방식(체이닝 방식)으로 구현해볼 수 있다. 이러한 방식을 우리는 링크드 리스트를 활용해서 구현이 가능하다.

 

 

링크드 딕트

# 해시 함수는 무작위로 숫자를 반환하는 것으로 인덱스 충돌이 생길 수 있음.
# 링크드 리스트를 활용하여 충돌을 막는 방법
# 체이닝 방식으로 새로운 키 벨류가 생성이 된다면 이전에 생성된 키 벨류 다음 노드로 연결되어 추가 되는 방식이라고 보면 된다. 
class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v

class LinkedDict:
    def __init__(self):
        self.items = [LinkedTuple()] * 8

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

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


linked_dict = LinkedDict()
linked_dict.put('test1', 1)
linked_dict.put('test2', 2)
linked_dict.put('test3', 3)

print(linked_dict.get('test1'))
print(linked_dict.get('test2'))
print(linked_dict.get('test3'))

  딕트 안에 링크드 튜플 객체를 생성해서 원소가 추가될때마다 튜플 객체에 추가하는 방식이다. 이해하기 편하게 하기 위해 딕셔너리를 생성할때  리스트가 해당 인덱스의 벨류가 되겠고 새로운 k, v 가 들어올 때 마다 리스트에 튜플 형식으로 추가하는 방식! BFS, DFS 할 때 연결된 노드를 그래프로 나타낼 때 위와 같은 방법과 구조가 유사하다.