[자료구조] 해쉬 테이블 (python)

해쉬 테이블 (hash table)

해시 함수를 사용해 데이터를 다루는 기법 중 하나로, 데이터의 검색, 저장이 아주 빠르다.
ex) 파이썬의 딕셔너리
※ 딕셔너리의 내부는 배열로 구현되어 있고, 해쉬 함수를 통해 배열에 저장하고 조회한다

key를 통해 데이터에 접근할 수 있기 때문에, 모든 데이터를 순회하지 않아도 된다 -> 속도 빠름!

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

    # 데이터 삽입
    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index] = value

    # key값에 해당하는 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"))

• 해쉬함수를 사용해 내부 배열에 값을 저장한다.
  • 하지만 충돌의 가능성이 있다.
  • ex) 3번 자리에 데이터가 중복으로 들어간다면? 덮어씌워진다.

충돌 문제를 해결하는 하나의 방법인 Chaining방법
링크드 리스트를 사용한다.
중복되면 덮어씌워지는 것이 아니라, 기존에 있는 데이터 뒤로 연결된다.

class LinkedTuple:
    def __init__(self):
        self.items = list()

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


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

class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

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

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

• 내부 배열이 아닌 링크드 리스트(LinkedTuple)를 사용해 키,값을 담는다.