해시법(2)

해시법(2) - 오픈 주소법 (open addressing)

---

오픈 주소법 (open addressing)은 해시 충돌시 사용하는 해결법이다. 다만 해시 체인법의 연장선은 아닌 다른 개념의 해결법이다.

어떤 한 원소를 추가할 때, 해당하는 버킷에 이미 다른 원소가 있을 경우, 재해시를 하여 그 옆에 있는 버킷을 살펴본다. 이 때 발생할 수 있는 문제점은 어떤 해시키를 가지고 있는 원소를 삭제했으면 해당 인덱스에 있는 버킷은 비어져 있으므로 자칫 같은 해시키를 가진 다른 원소의 검색이 실패할 수 있다는 것이다. 이를 통해 해당 인덱스의 버킷에 있는 원소를 삭제했을 경우, 따로 표시를 해두어 혼동하지 않게 한다.

예를 들어, 2와 15의 해시값은 2로 동일하다. 2는 인덱스 2에, 15는 오픈 주소법에 의해 인덱스 3에 저장되어 있다고 하고, 2를 삭제했다고 하면 인덱스 2는 삭제된 상태로 남겨진다. 때문에 15를 찾는다고 해도 인덱스 2는 ‘비워져 있는 상태’가 아닌 ‘삭제된 상태’이므로 정상적으로 그 다음 인덱스로 넘어가서 15를 찾을 수 있게 된다.

그렇기 때문에 각 인덱스 테이블은 상태가 총 3가지로 존재한다. EMPTY, OCCUPIED, 그리고 DELETED로 나뉘어져 있다.

오픈 주소법의 특징은 ‘검색’기능에서 찾을 수 있다. 아래 코드가 위에서 말한 EMPTY상태와 DELETED 상태를 구분해준다.

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

    for i in range(self.capacity):
        if p.stat == Status.EMPTY: 
            break
        elif p.stat == Status.OCCUPIED and p.key == key:
            return p
        hash = self.rehash_value(hash)
        p = self.table[hash]
    return None 

이전에 해당 인덱스에서 원소가 사라진 적이 있는 경우, DELETED상태로 되어 있으므로 break하지 않고 for문을 실행한다. 찾는 key값이 나올 때 까지 for 문이 실행되고, key값이 발견되면 해당 테이블의 노드를 return한다. Return한 노드는 search 메서드에서 활용되어 우리가 원하는 결과를 얻는다.