해시법(1)

해시법(1) - 체인법

해시법은 원소의 갯수가 n개일 경우, 배열을 n개나 만들어야 하는 기존의 문제점을 해결하기 위해 만든 법이다.

특정 규칙 (ex. 문자의 갯수, 나머지 등)을 통해 a개의 배열로 한정지으므로 n이 아무리 커도 n에 무관하게 딱 a개의 배열만 나오므로 시간 복잡도가 O(1)이라는 장점이 있다.

해시법에는 해시노드가 사용되는데, 해시노드는 key(고유 숫자), value (실질적인 값), 그리고 next (연결된 다음 해시 노드를 참조할 포인터)로 구성되어 있다.

해시 배열은 해시테이블 X 원소 갯수(capacity)만큼 이루어져 있다. 나눗셈법으로 이루어진 해시를 예로 들면, 각 해시테이블에는 key를 capacity로 나눈 해시값에 따라 정렬되어 있으며 해시노드는 상응되는 해시값과 연결된다. 예를 들어 33같은 경우 해시 값을 구하는 함수인 hash_value에 따라 고유 해시값인 (33%13) 7에 해당하는 해시 테이블에 연결된다.

def hash_value(self, key:Any)->int:
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(),16) % self.capacity)

이 부분이 해시값을 구하는 부분인데, key값이 int형일 경우 나눗셈법을 통해 해시값을 구하고, 그 외의 형태일 경우는 sha256 알고리즘을 통해 해시값을 구한다

원소 추가

---

add함수는 7에 해당하는 해시 테이블에 원소가 없으면 해시 테이블이 33해시노드를 참조하도록 한다. 만약 원소가 있으면 (ex 20) 해당 해시 테이블은 이미 20을 참조하고 있는 상태이므로, 동일한 해시 테이블을 next로 가지고 있는 33해시노드를 생성한 후(이 때 33해시노드는 20해시노드를 next를 통해 참조한 형태가 된다. 또한 next의 종류는 노드 포인터다), 7 해시 테이블이 33해시노드를 참조하도록 한다. (self.table[hash] = temp)

    def add(self, key:Any, value: Any) -> bool:
        hash = self.hash_value(key)
        p = self.table[hash]

        while p is not None: #this while statement checks if the same key exists
            if p.key == key:
                return False
            p = p.next

        temp = Node(key, value, self.table[hash]) #First, make the 'New Node, and the empty table(=self.table[hash]) moves to the New Node's 'next'
        self.table[hash] = temp #makes the existing hash table point the New Node(=temp)
        return True    

원소 제거

---

remove 함수는 예를들어 7 해시 테이블에 33->20 해시노드 순서로 연결되어 있고, 20을 없애고 싶으면 해시노드 포인터 p와 pp(pp는 None으로 초기화한다)를 만들고 p가 pp보다 한단계 앞선 상태로 만든다. p가 20에 도달할경우 20해시노드의 next는 none인 상태이므로, 20해시노드를 가리키고 있는 33해시노드의 next에, none을 가리키고 있는 20해시노드의 next를 대입 시킨다. 그렇게 되면 33해시노드는 none을 가리키고 있게 되므로 20은 연결이 끊어진 것이나 마찬가지다. 20을 건너뛰었다고 생각하면 된다.

def remove(self, key: Any) -> bool:
        hash = self.hash_value(key)
        p = self.table[hash]
        pp = None

        while p is not None:
            if p.key == key:
                if pp is None: #if there's only one element at following hash
                    self.table[hash] = p.next
                else:
                    pp.next = p.next #switches the node's next (pp points) to the other node's next (p points)
                return True
            pp=p
            p=p.next
        return False