[기본개념] Hash Table 구조

해시테이블은 기본적으로 dictionary라고 생각하면 된다

 

 

요런 느낌으로, hash function에 따라 키의 주소가 부여되고, 그 주소에 저장되게 된다

특징으로는

1. One - way

key를 넣어서 ==>  full dict & 주소가 나오는거지

그 반대로 주소를 넣어서 key를 얻을수는 없다

 

2. Deterministic

곧, 특정 Hash function에 의해서 특정 주소가 반환된다고 기대할 수 있다는 것.

랜덤이 아니라는 말이다.

 

* Collision : 같은 주소에 2개 이상의 값이 틀어갈 때 충돌이 발생하는 것

 

 

대표적인 충돌 해결 방법

* Chainigng :

ex) seperate chaining : 같은 주소에 hashing된 여러개의 dict을 Linked List로 연결해서 집어넣는 방식이라는 뜻이다

 

* Open Addressing : 모든 키를 해시 테이블 자체에 저장테이블의 각 칸(slot)에는 1개의 키만 저장

ex ) Linear Probing : 가장 가까운 빈 칸을 찾아서 넣는 방식 (Open addressing 의 일종). 단, 이렇게 되면 값들이 점점 연속으로 뭉쳐서 큰 cluster를 생성하는데, 이렇게 되면 검색시간이 클러스터의 길이에 비례하게 되므로 바람직하지 않다

ex ) Quadratic probing : 조금씩 더 건너뛰어서 저장하는 방식이다.  충돌 발생시 h(k), h(k) + 1^2, h(k) + 2^2, h(k) + 3^2, … 순서로 시도

 

ex ) Double hashing
서로 다른 두 해시 함수 h1과 h2를 이용한다.키 값에 따라서 해시 값이 달라진다.

 

 

 

| 기본 구조

그냥 None값으로 채운 기본 리스트 구조를 만든다

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

 

키를 넣으면 그게 들어갈 주소를 뱉어내는 hash함수를 만든다 (기본 제공)

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)
            
    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash

 

 

| Set Item (insert같이 그 자리에 딕셔너리를 넣는 함수)

 

    def set_item(self, key, value):
        index = self.__hash(key)
        if self.data_map[index] is None:
            self.data_map[index] = []
        self.data_map[index].append([key,value])

 

일단, hash 함수를 이용해서 주소를 뽑아내고,

우리가 가진 hash table의 해당 주소가 비어있는 경우, 거기에 새로운 빈 리스트를 생성한다

그리고 그 자리에, 우리의 [key, value] 리스트를 삽입해준다. 간단! 

 

 

| Get Item (key값이 주어지면 value를 찾는 함수)

    def get_item(self, key):
        index = self.__hash(key)
        if self.data_map[index] is not None:
            for i in range(len(self.data_map[index])):
                if self.data_map[index][i][0] == key:
                    return self.data_map[index][i][1]
        return None

 

너무 쉽게 잘 풀어냈다

일단 key가 주어지면, 그게 저장돼있는 index값을 해쉬함수로 받아내고

그 주소  안에 리스트가 있을 수 있잖나  [ [키:밸], [키2:밸2], [키3:밸3], [키4:밸4], [키5:밸5] ] 이런 식으로!

그러면 for 루프를 돌면서, 해당 리스트의 0번값(키)가 일치하면

해당 리스트의 1번값(밸류)를 반환하는거다

 

base case로, 그 키가 맵 안에서 찾을 수 없다면 None을 반환 ! 

 

 

| Keys (해쉬테이블의 모든 키를 리스트로 반환)

역시 완벽하게 풀어냈다 !! 

    def keys(self):
        all_keys = []
        for i in range(len(self.data_map)):
            if self.data_map[i] is not None:
                for j in range(len(self.data_map[i])):
                    all_keys.append(self.data_map[i][j][0])
        return all_keys

 

빈 리스트를 생성하고,

루프를 두 번 돌아야 한다는 단점이 있다.

해쉬테이블 전체를 루프 돌아야하고, 그 안에서 또 그 리스트 길이만큼 루프를 돌면서 각각의 [키:밸] 들의 [0] 인덱스인 키를 빈 리스트에 append해준다.

최종적으로 그 리스트를 return 해주는거다! 

 

 

| Big-O

set : O(1) 그냥 단순 삽입이니까. hash + append

get : O(1) 해쉬의 해당 주소에서 리스트 길이만큼 돌아야하니까 O(n)이라 생각할 수 있겠지만, 사실 한 주소 안에 들어갈만한 값이 그렇게 많지도 않고, 적절히 분배를 해준다는 전제가 있다. 그리고 hash table 크기도 엄청 큭ㄹ거기 때문에, O(n)까지 갈 일은 없다고 간주.

 

결국, insert, lookup 모두 다 O(1) 인거다!! 

하지만 O(1)이라고 해서, 검색을 할 때 BST(O(logn))보다 무조건 좋은 것은 아니다! BST는 값이 sorted 되어있기 떄문에, 더 효율적일 수 있다 ! 

 

key : O(n^2)