해시 함수 와 해시충돌

강사님: 김용담

개요

해시함수와 해시충돌의 개념에 대해서 알아보았습니다.

해시 함수란?

해시 충돌에 앞서 해시 함수에 대해서 알아보겠습니다.

Hash Brown

[ Hash Brown]

해시 브라운이라는 요리는 감자를 잘게 썰어 튀긴 요리이다. 해시라는 단어의 의미는 잘게썬다라는 의미를 가지고 있습니다.

즉, 해시 함수에 데이터를 넣으면 처음의 값이 아닌 알아볼수 없는 고정된 길이의 데이터로 출력하는 함수입니다.
해시 함수를 통해 얻어진 값을 해시 값, 해시코드 라고 합니다. ^1

해쉬함수 코드

if __name__ == "__main__":  
    print(hash("hello"))
    # 출력 : 4757455132936133864

앞서 설명한것과 같이 "hello" 글자가 "4757455132936133864" 데이터로 변환 된것을 알 수 있습니다.

해시함수를 왜 사용하는가?

해시함수는 해시테이블이라는 자료구조에서 사용된다. 해시코드를 통해 빠른 탐색이 가능하기 때문입니다.
용도로는 데이터 베이스 검색, 테이블 데이터 검색 등에서 사용가능합니다.
해시함수의 특징으로는 원래의 데이터를 계산적으로는 알기 힘들고 결정론적이어야 한다는 것입니다. 그리고 같은 데이터 라면 해시코드도 동일해야한다는 특성을 가지고 있습니다. 이러한 특성으로 암호학과 데이터 무결성에서도 사용됩니다.

코드로 알아보기

if __name__ == "__main__":  
    print(hash("hello") == hash("hello"))  # True

테스트를 통해 같은 해시값을 보장하는것을 알 수 있습니다.

다음으로는 해시테이블로 알아보겠습니다.

해시 테이블

해시 테이블은 key, value 쌍으로 데이터를 저장하는 자료구조입니다.

pseudocode 알아보기

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

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        self.table[index] = value

    def get(self, key):
        index = self._hash(key)
        return self.table[index]

# 사용 예시
if __name__ == "__main__":
    hash_table = HashTable()

    # 데이터 삽입
    hash_table.insert("name", "Alice")
    hash_table.insert("age", 25)

    # 데이터 검색
    print(hash_table.get("name"))  # Alice
    print(hash_table.get("age"))   # 25

1. 해시 함수로 저장위치 계산

def _hash(self, key):
    return hash(key) % self.size

해시 함수를 통해서 테이블의 저장할 위치를 계산합니다.

2. 삽입(Insert)

def insert(self, key, value):
    index = self._hash(key)
    self.table[index] = value

해시 값을 테이블의 index(위치)에 저장합니다.

3. 조회(Get)

   def get(self, key):
    index = self._hash(key)
    return self.table[index]

해시값을 통해 O(1) 의 시간복잡도로 빠르게 탐색 할 수 있습니다.

Hash Collision(해시 충돌)

해시 충돌이란 해시테이블에서 사용되는 해시 값이 전혀 다른 데이터인데도 동일한 해시 값을 공유할때 발생하는 문제입니다.

충돌 시뮬레이션

class HashCollisionTable:  
    def __init__(self, size=5):  
        self.size = size  
        self.table = [None] * size  

    def _hash(self, key):  
        return key % self.size  

    def set(self, key, value):  
        index = self._hash(key)  
        self.table[index] = value  

    def get(self, key):  
        index = self._hash(key)  
        return self.table[index]

# 테스트: 충돌 상황 만들기  
if __name__ == "__main__":  
    hash_table = HashCollisionTable(10)  

    keys = [1, 11, 21]  # 같은 해시값을 가짐  
    for key in keys:  
        hash_table.set(key, f"value_for_{key}")  

    # 삽입된 데이터 확인  
    for key in keys:  
        print(f"{key}: {hash_table.get(key)}")  

    # 테이블 상태 확인  
    for i, slot in enumerate(hash_table.table):  
        print(f"Slot {i}: {slot}")

결과

HashTable Slots:
Slot 0: None
Slot 1: value_for_21
Slot 2: None
Slot 3: None
Slot 4: None
Slot 5: None
Slot 6: None
Slot 7: None
Slot 8: None
Slot 9: None

hash함수의 로직을 key % self.size 으로 구현해 놓고 [1,11,21] 을 넣으면 계산되는 해시값이 모두 1 로 동일하여 같은 index 위치에 들어가질 조건이 발생하여 충돌이 발생합니다.

해시충돌 해결방법

해결하는 방법으로는 Separate Chaining과 Open Addressing or Closed Hashing(Open Addressing 이라고 하겠음) 방법이 있습니다.

• Linear probing(선형 프로빙)
  선형 프로빙은 해시값 인덱스에서 부터 비어있는 슬롯이 발견될때까지 검색하여 저장하는 방법입니다.

pseudocode 출처

class LinearProbeHashTable:  
    def __init__(self, size):  
        self.size = size  
        self.keys = [None] * size  
        self.values = [None] * size  

    def hash_function(self, key):  
        return int(key) % self.size  

    def put(self, key, value):  
        index = self.hash_function(key)  

        # Linear probing to find an empty slot  
        while self.keys[index] is not None:  
            if self.keys[index] == key:  
                # If key already exists, update its value  
                self.values[index] = value  
                return  
            index = (index + 1) % self.size  

        # Insert the key-value pair  
        self.keys[index] = key  
        self.values[index] = value  

    def get(self, key):  
        index = self.hash_function(key)  

        # Linear probing to find the key  
        while self.keys[index] is not None:  
            if self.keys[index] == key:  
                return self.values[index]  
            index = (index + 1) % self.size  

        # Key not found  
        return None  


if __name__ == "__main__":  
    hash_table = LinearProbeHashTable(10)  
    hash_table.put('1', 5)  
    hash_table.put('11', 7)  
    hash_table.put('21', 3)  

    print(hash_table.get('1'))
    print(hash_table.get('11')) 
    print(hash_table.get('21'))

문제점

1. 클러스터링 문제
   충돌이 발생 후 슬롯에 데이터를 형성하는 과정에서 클러스터링(그룹)이 형성되게 됩니다. 충돌이 많이 질수록 그룹의 크기가 거치면 검색 및 삽입속도가 저하 됩니다.
2. 삭제 복잡성 문제
   예시 상황

{
    1: "A"
    2: "B"
}

# 데이터 "C" 해시값이 2라고 가정, 빈 슬롯을 찾아 다음 슬롯에 데이터를 넣습니다.
{
    1: "A"
    2: "B"
    3: "C"
}

# B가 삭제 됩니다.
{
    1: "A"
    2: empty
    3: "C"
}

# C를 조회, "C" 해시값은 2이므로, 데이터를 찾을 수 없음

이러한 문제를 해결하기 위해 삭제시 delete 를 마킹해주어야합니다.

{
    1: "A"
    2: -1
    3: "C"
}

이렇게 해주어야 삭제 되었으니 다음 슬롯으로 탐색할것입니다. 이러한 부분때문에 복잡성이 증가 됩니다.

• Quadratic probing
  선형 프로빙과 비슷합니다. 차이점은 k^2 즉 제곱 만큼 떨어진 슬롯을 찾으므로 멀리 떨어트려서 1차 클러스터링을 방지하는 것입니다. 하지만 이는 여전히 2차 클러스터링을 발생하는 문제가 있습니다.
• Double hashing 참고
  더블 해싱은 Linear probing, Quadratic probing 문제인 클러스터링 문제를 해결 할 수 있습니다. 더블해시 이름 그대로 두개의 해시함수를 사용합니다.

1. 첫번째 해시 함수는 일반적으로 사용하는 형태입니다.

   hash1(key) = key % TABLE_SIZE

2. 2번째 해시함수

   hash2(key) = PRIME – (key % PRIME)
   # PRIME은 TABLE_SIZE보다 작은 소수이어야 합니다.

• 이중 해시함수로 균일하게 데이터를 분포 시켜줍니다.
• 클러스터링을 형성하지 않습니다.
• 충동을 방지해줍니다.

예시코드

def __hash1(self, value: int) -> int: 
    return value % self.TABLE_SIZE
def __hash2(self, value: int) -> int: 
    return self.PRIME - (value % self.PRIME)

# 프로빙을 위한 해시 재조합
probe, offset = self.__hash1(value), self.__hash2(value) 
while self.hashTable[probe] != -1: 
    probe = (probe + offset) % self.TABLE_SIZE

 

마무리

해시함수와 해시충돌에 대해서 알아보았습니다.

다양한 예시 코드를 작성해봄으로써 개념을 좀 더 깊게 이해할 수 있었습니다.