9. 해시법

---

 

 

1. 정렬된 배열에 원소를 추가하는 알고리즘

이진 검색으로 원소가 추가될 위치를 확인한다.

검색 실패 시, 중앙에 위치한다.

원소가 이동하는 데 필요한 시간 복잡도는 O(n)이다.

원소 삭제 시에도 동일한 비용이 발생한다.

 

---

 

2. 해시법 (Hashing)

해시법이란, 간단한 연산을 통해 데이터를 저장할 위치를 구하는 방법이다.

원소의 검색 외에 추가 및 삭제 작업도 효율적으로 구현할 수 있다.

데이터의 저장과 검색에 극단적인 효율을 가지고 있어 빠른 응답을 요구하는 프로그램에 활용된다.

해시값 (Hash Value)이란, 해시법을 통해 계산된 데이터 저장 위치(인덱스)를 말한다.

해시 테이블 (Hash Table)이란, 해시값을 인덱스로 하는 배열을 말한다.

버킷 (Bucket)이란, 해시 테이블에서 원소가 실제로 저장되는 장소(슬롯: Slot)를 말한다.

해시 함수 (Hash Function)란, 원소를 해시 테이블에 저장하기 위해 해시값을 계산하는 함수를 말한다.

해시 함수는 해시 테이블의 크기가 m일 때, 0에서 (m-1) 사이의 값을 반환한다. (h(x) = x mod m)

해시 함수는 계산이 간단하며, 해시값이 고르게 분산되도록 설계해야 한다.

 

---

 

3. 충돌 (Collision)

충돌이란, 새로운 원소를 추가하려고 할 때, 버킷이 중복되는 현상이다.

같은 해시 값을 가지는 원소가 존재할 때 발생한다.

충돌 문제를 해결하기 위한 방법은 다음과 같다.

• 체인법 (Chaining Method): 해시값이 같은 원소를 연결 리스트로 관리하는 방법이다.
• 오픈 주소법 (Open Address Method): 빈 버킷을 찾을 때까지 해시를 반복 수행하는 방법으로, 충돌이 발생해도 해시 테이블 공간 내에서 해결한다.

 

3.1) 체인법 (Chaining Method)

해시값이 같은 데이터를 체인(chain) 모양의 연결 리스트로 연결한다.

해시 테이블의 각 버킷은 해시값이 동일한 원소의 연결 리스트 헤드 노드를 참조한다.

오픈 해시법(Open Hashing)이라고도 부른다.

 

3.2) 체인법을 사용해 해시 프로그램 구현하기

체인법으로 해시 프로그램을 구현하기 위해서는 먼저 Node 클래스를 생성해야 한다.

Node 클래스는 자기 참조형 클래스이며, 아래 사진처럼 연결 리스트 구조를 취한다.

from __future__ import annotations
from typing import Any, Type
import hashlib


class Node :
    def __init__ (self, key: Any, value: Any, next: Node) -> None :
        self.key = key      ## 키
        self.value = value  ## 값
        self.next = next    ## 뒤쪽 노드 참조

class ChainedHash :
    def __init__(self, capacity: int) -> None :
        self.capacity = capacity
        self.table = [None] * self.capacity
        
    
    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)
    
    
    def search(self, key: Any) -> Any :
        hash = self.hash_value(key)
        p = self.table[hash]
        
        while (p is not None) :
            if (p.key == key) :
                return p.value
            p = p.next
            
        return None
        
        
    def add(self, key: Any, value: Any) -> bool :
        hash = self.hash_value(key)
        p = self.table[hash]
        
        while (p is not None) :
            if (p.key == key) :
                return False
            p = p.next
            
        temp = Node(key, value, self.table[hash])
        self.table[hash] = temp
        
        return True
        
    
    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) :
                    self.table[hash] = p.next
                else :
                    pp.next = p.next
                
                return True
            
            pp = p
            p = p.next

        return False
        
        
    def dump(self) -> None :
        for i in range(self.capacity) :
            p = self.table[i]
            print(i, end='')
            
            while (p is not None) :
                print(f"    -> {p.key} ({p.value})", end='')
                p = p.next
            print()

 

---

 

4. 오픈 주소법 (Open Addressing Method)

충돌이 발생했을 때 재해싱(Rehashing)을 수행하여 빈 버킷을 찾는 방법으로, 빈 버킷이 나올 때까지 해싱을 반복한다.

 

4.1) 원소 추가하기

충돌이 발생하면 재해싱을 위한 해시 함수로 새로운 해시값을 계산한다.

선형 탐사법(Linear Probing)을 사용한다.

 

4.2) 원소 삭제하기

원소 삭제 시, 버킷을 그냥 비우기만 하면 재해싱된 데이터에 대한 검색이 실패할 수 있다.

버킷이 비어 있는 상태인지, 삭제 처리된 상태인지를 구분해야 한다.

 

4.3) 원소 검색하기

버킷이 비어 있을 경우, 검색에 실패한다.

버킷이 비어 있지 않을 경우, 재해싱을 반복하며 원하는 값을 찾을 때까지 검색을 이어나간다.

원하는 값을 찾았다면 검색에 성공한다.

 

---

 

---

수고하셨습니다!

---