개발하는데 다 이유가 있겠지

해시 테이블(Hash Table)

Key, Value로 데이터를 저장하는 자료구조

내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 떄문에 데이터 검색할 수 있음

• 시간복잡도 O(1)  -> Search(검색), Insert(삽입), Delete(삭제)
• 해시값으로 변환하는 과정을 '해시 함수(Hash Function)'이라고 함
• 저장할 배열(버킷)이 중복되는 현상 -> 해시 충돌(Collsion)

해시법

• 데이터 저장 위치 = 인덱스
• 데이터 추가 또는 삭제가 빈번한 경우 효율적으로 수행 가능
• 해시(hash)란 특정 연산의 결과 값(데이터 접근시 사용)
• 원소값을 해시값으로 변환하는 과정 -> 해시 함수(Hash Function)

해시 충돌 처리방법

• 체인법(Chaining) : 해시값이 같은 원소를 연결 리스트로 관리 
  • 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결함
  • 오픈 해시법(Open Hasing)이라고도 부름
  • 각 버킷(배열)의 인덱스를 해시값으로 하는 연결 리스트의 앞쪽노드를 참조
    • 크기가 클수록 충돌발생 방지 가능하지만, 메모리 낭비가 커짐
    • 크기가 작을수록 충돌발생 가능성 커지지만, 메모리 소모가 작음
  • Node(key, value, next) : 키, 값, 뒤쪽 노드

• 노드 초기화

class Node:
    def __init__(self, key: any, value: any, next) -> None:
        self.key = key      # 키 초기화
        self.value = value  # 값 초기화
        self.next = node    # 참조 노드 초기화

• 버킷(배열 초기화)

class ChainedHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity            # 해시 테이블의 크기 초기화
        self.table = [None] * capacity      # 해시 테이블 초기화

• Key 타입별 처리방식
  • Key는 모든 데이터 타입으로 입력되며, 정수인 경우와 아닌 경우로 구분
    • 정수인 경우 : key를 capacity로 나눈 나머지를 해시값으로 반환
    • 정수가 아닌 경우 : 나머지를 구하는 연산이 불가능하므로 표준 라이브러리 hashlib를 사용하여 key의 자료형을 변환한 이후에 capacity로 나눈 나머지를 해시값으로 반환

import hashlib

class ChainedHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity            # 해시 테이블의 크기 초기화
        self.table = [None] * capacity      # 해시 테이블 초기화

    # 해시 함수
    def hash(key: any) -> int:
        if isinstance(key, int):        
            return key % self.capacity            # key가 정수인 경우
        byte_str = str(key).encode()            # key → str 변환 후 바이트 문자열 생성
        byte_hash = hashlib.sha256(byte_str)    # 주어진 바이트 문자열의 해시값
        key = byte_hash.hexdigest()                # 해시값을 16진수 문자열로 변환
        return int(key, 16) % self.capacity        # key가 정수가 아닌 경우

• Key로 원소 검색

class ChainHash:

    # ...(중략)...

    def search(self, key: any) -> any:
        hash_value = self.hash(key)        # 해시값
        ref = self.table[hash_value]    # 참조 노드

        while ref is not None:            
            if ref.key == key:            # 연결 리스트 노드에서 key를 찾은 경우
                return ref.value
            ref = ref.next

        return None                        # 연결 리스트 노드에서 key를 찾지 못한 경우

• 새로운 참조노드 추가

class ChainHash:

    # ...(중략)...

    def add(self, key: any, value: any) -> bool:
        if self.search(key) is not None:
            return False                # 이미 등록된 key
        hash_value = self.hash(key)     # 해시값
        ref = Node(key, value, self.table[hash_value])
        self.table[hash_value] = ref
        return True                     # 등록 완료

• Key값으로 삭제
  • 맨 앞의 노드를 삭제하면 뒤에 참조노드 모두 삭제될 수 있음
  • 참조노드 앞의 노드의 유무에 따라 다음 노드를 앞으로 한 칸씩 당김

class ChainHash:

    # ...(중략)...

    def remove(self, key: any) -> bool:
        hash_value = self.hash(key)     # 해시값
        ref = self.table[hash_value]    # 참조 노드
        pref = None                     # 참조 노드 앞의 노드
        while ref is not None:
            if ref.key == key:
                if pref is None:        # 앞의 노드가 없는 경우
                    self.table[hash_value] = ref.next
                else:                   # 앞의 노드가 있는 경우
                    pref.next = ref.next
                return True
            pref = ref
            ref = ref.next
        return False

---

• 오픈 주소법(선형 탐사법) : 빈 버킷을 찾을 때까지 해시를 반복
  • 재해시(rehasing)를 통해 빈 버킷을 찾는 방법 == 닫힌 해시법(Closing hasing)
  • 재해시 규칙은 사용자가 자유롭게 정할 수 있음
  • Bucket, Attribute 클래스가 필요함

해시값(원소값%8)	0	1	2	3	4	5	6	7
원소값	16	1	10	8	22	13	6	7

-> 16 삭제

해시값(원소값%8)	0	1	2	3	4	5	6	7
원소값	None	1	10	8	22	13	6	7

-> 8 삭제 시도하면 해시값이 0이기 때문에 8을 검색하지 못함

--> 아래와 같이 속성을 부여하면 됨 

• 속성 부여(Enum)

from enum import Enum

class Attribute(Enum):
    SAVED = 0        # 데이터 저장 상태
    NULL = 1        # 비어있는 상태
    DELETED = 2        # 삭제된 상태

해시값(원소값%8)	0	1	2	3	4	5	6	7
원소값	Deleted	1	10	8	22	13	6	7

 

• 버킷(배열) 클래스(key, value, attribute)

class Bucket:
    def __init__(self, key: any = None, value: any = None, 
                 attribute: Attribute = Attribute.NULL) -> None:
        self.key = key              # 키 초기화
        self.value = value          # 값 초기화
        self.attribute = attribute  # 속성 초기화

    def set(self, key: any, value: any, attribute: Attribute) -> None:
        self.key = key              # 키 변경
        self.value = value          # 값 변경
        self.attribute = attribute  # 속성 변경

       def set(self, attribute: Attribute) -> None:
        self.attribute = attribute  # 속성 변경

• 오픈 주소법 코드

import hashlib

class OpenHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity                # 해시 테이블의 크기 초기화
        self.table = [Bucket()] * capacity        # 해시 테이블 초기화

    def hash(self, key: any) -> int:
        if isinstance(key, int):
            return key % self.capacity          # key type == int
        byte_str = str(key).encode()            # key → str 변환 후 바이트 문자열 생성
        byte_hash = hashlib.sha256(byte_str)    # 주어진 바이트 문자열의 해시값
        key = byte_hash.hexdigest()             # 해시값을 16진수 문자열로 변환
        return int(key, 16) % self.capacity     # key type == int

    def rehash(self, key: any) -> int:
        hash_value = self.hash(key) + 1
        return hash_value % self.capacity

• 해시값에 해당하는 버킷 찾기

class OpenHash:

    # ...(중략)...

    def bucket(self, key: any) -> any:
        hash_value = self.hash(key)
        bucket = self.table[hash_value]
        for i in range(self.capacity):
            if bucket.attribute == Attribute.NULL:
                break
            elif bucket.attribute == Attribute.SAVED and bucket.key == key:
                return bucket
            hash_value = self.rehash(hash_value)    # 재해시 수행
            bucket = self.table[hash_value]
        return None

• Key로 원소 검색

class OpenHash:

    # ...(중략)...

    def search(self, key: any) -> any:
        bucket = self.bucket(key)
        if bucket is not None:
            return bucket.value
        else:
            return None

• 원소 추가
  • 모든 버킷에 원소가 저장되면 더 이상 추가로 저장할 수 없음

class OpenHash:

    # ...(중략)...

    def add(self, key: any, value: any) -> bool:
        if self.search(key) is not None:    # 이미 등록된 키
            return False
        hash_value = self.hash(key)
        bucket = self.table[hash_value]
        for i in range(self.capacity):
            if bucket.attribute == Attribute.NULL or bucket.attribute == Attribute.DELETED:
                self.table[hash_value] = Bucket(key, value, Attribute.SAVED)
                return True
            hash_value = self.rehash(hash_value)  # 재해시 수행
            bucket = self.table[hash_value]
        return False

• 원소 삭제

class OpenHash:

    # ...(중략)...

    def remove(self, key: any) -> int:
        bucket = self.bucket(key)
        if bucket is None:
            return False
        bucket.set_attribute(Attribute.DELETED)
        return True

 

 

 

[출처] https://choewy.tistory.com/99#%EC%B2%B4%EC%9D%B8%EB%B2%95