코딩한걸음
Published 2023. 8. 22. 09:00
[자료구조] 해시 테이블 (Hash Table) CS/Algorithm
728x90
반응형
본 포스트는 필자가 학습하고 작성한 글이기 때문에 틀린내용이 있을 수 있습니다.

 

해시 (Hash)

해시는 데이터를 다른 데이터로 매핑하는 프로세스를 의미한다.

이를 위해 해시 함수를 사용하여 어떤 값을 고정된 크기의 값으로 변환한다.

 

해시 함수 (Hash Funtion)

  • 입력 받은 값을 '일정한 길이의 해시 값'으로 변환
  • 동일한 입력 값에 대해서는 항상 동일한 출력 값(해시 값 or 해시 코드)을 반환
  • 작은 입력 값의 변화에도 출력 값이 크게 바뀐다(높은 민감도)

해시 테이블 (Hash Table)

해시 테이블은 키와 값의 쌍을 저장하는 데이터 구조다.

 

핵심 요소

  • 키 (Key) : 유일한 값으로, 해시 함수를 통해 해시 값으로 변환
  • 해시 함수 (Hash Funtion) : 키를 받아 해시 값을 반환하는 함수
  • 해시 값 (Hash Value) or 해시 코드 (Hash Code) : 키를 해시 함수에 넣었을 때 나오는 결과값
  • 버킷 (Bucket) or 슬롯 (Slot) : 해시 테이블 내의 위치나 주소를 의미하며, 해시 값에 따라 키-값 쌍이 저장

장점

  • 일반적인 경우, O(1)의 시간 복잡도를 가지며 데이터의 검색이 매우 빠르다.
  • 키-값 쌍의 삽입과 삭제도 빠르다.

단점

  • 해시 충돌을 해결하기 위한 추가적인 메커니즘이 필요하다.
  • 해시 함수와 메모리 사용량에 따라 공간 복잡도가 높을 수 있다.
  • 해시 테이블의 크기를 조정해야 할 필요가 있을 때(리사이징) 비용이 발생한다.

리사이징을 하는 이유

  • 해시 테이블의 로드 팩터 (Load Factor)가 특정 임계값을 초과 할 때 :
    로드 팩터는 테이블 내에 저장된 항목의 수를 테이블의 전체 크기로 나눈 값이다.
    로드 팩터가 높아지면 해시 충돌의 확률이 증가하므로, 성능이 저할될 수 있다.
    이를 방지하기 위해 테이블 크기를 늘리는 것이 필요하다.
    일반적으로 로드 팩터는 0.25 ~ 0.75 에서 효율이 좋다고 한다.
  • 공간 효율성을 위해 :
    해시 테이블에서 많은 항목들이 삭제되어 로드 팩터가 매우 낮아진다면, 메모리를 비효율적으로 사용하게 된다.
    이런경우, 테이블의 크기를 줄여 공간 효율성을 높일 수 있다.

동작 원리

  1. 키-값 쌍을 저장하거나 검색할 때 해시 함수에 넣어서 해시 값을 얻는다.
  2. 이 해시 값은 버킷의 인덱스로 사용되어 키-값 쌍이 해당 버킷에 저장되거나 검색된다.
  3. 동일한 해시 값을 갖는 다른 키(해시 충돌)가 있을 경우, 다양한 충돌 해결 전략을 사용한다.

해시 충돌 처리 방법

  • 개방 주소법 (Open Addressing) : 충돌이 발생하면 다른 주소에 데이터를 저장
    • 선형 탐사 : 일정한 간격으로 다음 버킷을 탐색
    • 제곱 탐사 : 버킷의 인덱스에 제곱을 더해 탐색
    • 이중 해싱 : 두번째 해시 함수를 사용하여 버킷을 탐색
  • 체이닝 (Chaining) : 같은 주소의 데이터를 연결 리스트로 연결하는 방법

구현

해시 테이블의 구현은 해시 함수, 리사이징을 하는 로드 팩터, 해시 충돌 처리 방법을 고려해 구현해야 한다.

해시 함수의 경우 추가적인 사항 없이(실제론 요구사항에 맞춰 추가적인 로직을 갖는다) python의 hash()를 써서 size로 나눈 나머지값, 해시 충돌 처리 방법은 위에 소개한 4가지 모두,  리사이징을 처리할 로드 팩터는 0.5로 설정했다.

 

체이닝을 사용한 해시 테이블

class Node:
    """연결 리스트의 노드를 위한 클래스"""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size
        self.count = 0  # 저장된 요소의 수

    def _hash(self, key):
        """해시 함수: 키를 받아 해시 값을 반환합니다."""
        return hash(key) % self.size

    def _resize(self, new_size):
        """해시 테이블의 크기를 조정합니다."""
        old_table = self.table
        self.size = new_size
        self.table = [None] * new_size
        self.count = 0  # 재삽입될 때 다시 계산

        for head_node in old_table:
            current = head_node
            while current:
                self.set(current.key, current.value)
                current = current.next

    def set(self, key, value):
        """키-값 쌍을 저장합니다."""
        index = self._hash(key)
        if self.table[index] is None:
            self.table[index] = Node(key, value)
        else:
            current = self.table[index]
            while current:
                # 이미 키가 있으면 값을 갱신
                if current.key == key:
                    current.value = value
                    return
                if current.next is None:  # 마지막 노드이면
                    current.next = Node(key, value)
                    break
                current = current.next

        self.count += 1
        # 요소 수가 테이블 크기의 절반을 초과하면 리사이징
        if self.count > self.size // 2:
            self._resize(2 * self.size)

    def get(self, key):
        """키에 해당하는 값을 반환합니다."""
        index = self._hash(key)
        current = self.table[index]
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return None

    def __str__(self):
        result = []
        for head_node in self.table:
            if head_node:
                current = head_node
                while current:
                    result.append(f"{current.key} : {current.value}")
                    current = current.next
        return "{"+", ".join(result)+"}"

 

검증

# 해시 테이블 테스트
test = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew", "kiwi", "lime", "mango"]
hash_table = HashTable()
for idx, value in enumerate(test):
    hash_table.set(value, idx)

print(hash_table)
# 6, 11 번째 set에서 리사이징이 일어난다. 10(default) > 20 > 40
print(hash_table.size)

 

선형 탐사를 사용한 해시 테이블

class LinearProbingHashTable:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
        self.count = 0  # 저장된 요소의 수

    def _hash(self, key):
        """해시 함수: 키를 받아 해시 값을 반환합니다."""
        return hash(key) % self.size

    def _resize(self, new_size):
        """해시 테이블의 크기를 조정합니다."""
        old_keys = self.keys
        old_values = self.values

        self.size = new_size
        self.keys = [None] * new_size
        self.values = [None] * new_size
        self.count = 0  # 재삽입될 때 다시 계산

        for key, value in zip(old_keys, old_values):
            if key is not None:
                self.set(key, value)

    def set(self, key, value):
        """키-값 쌍을 저장합니다."""
        index = self._hash(key)
        original_index = index

        # 선형 탐사
        while self.keys[index] is not None and self.keys[index] != key:
            index = (index + 1) % self.size
            if index == original_index:  # 전체 해시 테이블을 순회했으면 리사이징
                self._resize(2 * self.size)
                self.set(key, value)
                return

        # 새로운 키 삽입 시
        if self.keys[index] is None:
            self.count += 1

        self.keys[index] = key
        self.values[index] = value

        # 요소 수가 테이블 크기의 절반을 초과하면 리사이징
        if self.count > self.size // 2:
            self._resize(2 * self.size)

    def get(self, key):
        """키에 해당하는 값을 반환합니다."""
        index = self._hash(key)
        original_index = index

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
            if index == original_index:
                break

        return None

    def __str__(self):
        return "{"+", ".join([f"{k} : {v}" for k, v in zip(self.keys, self.values) if k is not None])+"}"

 

검증

# 선형 탐사 해시 테이블 테스트
test = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew", "kiwi", "lime", "mango"]
linear_hash_table = LinearProbingHashTable()
for idx, value in enumerate(test):
    linear_hash_table.set(value, idx)

print(linear_hash_table)
# 6, 11 번째 set에서 리사이징이 일어난다. 10(default) > 20 > 40
print(linear_hash_table.size)

 

제곱 탐사를 사용한 해시 테이블

class QuadraticProbingHashTable:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
        self.count = 0

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

    def _resize(self, new_size):
        old_keys = self.keys
        old_values = self.values
        self.size = new_size
        self.keys = [None] * new_size
        self.values = [None] * new_size
        self.count = 0

        for key, value in zip(old_keys, old_values):
            if key is not None:
                self.set(key, value)

    def set(self, key, value):
        index = self._hash(key)
        original_index = index
        distance = 1

        while self.keys[index] is not None and self.keys[index] != key:
            index = (original_index + distance ** 2) % self.size
            distance += 1
            if distance > self.size:  # 전체 해시 테이블을 순회했으면 리사이징
                self._resize(2 * self.size)
                self.set(key, value)
                return

        if self.keys[index] is None:
            self.count += 1

        self.keys[index] = key
        self.values[index] = value

        if self.count > self.size // 2:
            self._resize(2 * self.size)

    def get(self, key):
        index = self._hash(key)
        original_index = index
        distance = 1

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (original_index + distance ** 2) % self.size
            distance += 1
            if distance > self.size:
                break

        return None

    def __str__(self):
        return "{"+", ".join([f"{k} : {v}" for k, v in zip(self.keys, self.values) if k is not None])+"}"

 

검증

# 제곱 탐사 해시 테이블 테스트
test = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew", "kiwi", "lime", "mango"]
quadratic_hash_table = QuadraticProbingHashTable()
for idx, value in enumerate(test):
    quadratic_hash_table.set(value, idx)

print(quadratic_hash_table)
# 6, 11 번째 set에서 리사이징이 일어난다. 10(default) > 20 > 40
print(quadratic_hash_table.size)

 

이중 해싱을 사용한 해시 테이블

class DoubleHashingHashTable:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
        self.count = 0

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

    def _hash2(self, key):
        return 1 + (len(key) % (self.size - 1))

    def _resize(self, new_size):
        old_keys = self.keys
        old_values = self.values
        self.size = new_size
        self.keys = [None] * new_size
        self.values = [None] * new_size
        self.count = 0

        for key, value in zip(old_keys, old_values):
            if key is not None:
                self.set(key, value)

    def set(self, key, value):
        index = self._hash(key)
        original_index = index
        hash2 = self._hash2(key)

        while self.keys[index] is not None and self.keys[index] != key:
            index = (index + hash2) % self.size
            if index == original_index:
                self._resize(2 * self.size)
                self.set(key, value)
                return

        if self.keys[index] is None:
            self.count += 1

        self.keys[index] = key
        self.values[index] = value

        if self.count > self.size // 2:
            self._resize(2 * self.size)

    def get(self, key):
        index = self._hash(key)
        original_index = index
        hash2 = self._hash2(key)

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + hash2) % self.size
            if index == original_index:
                break

        return None

    def __str__(self):
        return "{"+", ".join([f"{k} : {v}" for k, v in zip(self.keys, self.values) if k is not None])+"}"

 

검증

# 이중 해싱 해시 테이블 테스트
test = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew", "kiwi", "lime", "mango"]
double_hash_table = DoubleHashingHashTable()
for idx, value in enumerate(test):
    double_hash_table.set(value, idx)

print(double_hash_table)
# 6, 11 번째 set에서 리사이징이 일어난다. 10(default) > 20 > 40
print(double_hash_table.size)

 

 

 

 

728x90
반응형
저작자표시 비영리 변경금지
profile

코딩한걸음

@Joonyeol_Yoon

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

검색 태그

가상환경
코딩테스트
DRF
백준
덩크로우
WIL 주간회고
50문 50답
머신러닝
Algorithm
baekjoon
코드리뷰
내일배움캠프
dfs
KPT회고록
python
Django
자료구조
TIL일지
나이키
다익스트라
주니어 개발자
알고리즘
자료형
스파르타코딩클럽
TIL 일지
BFS
포스트맨
프로그래머스
문자열 자료형
문제풀이

티스토리툴바