해시 테이블

1. 용어정리

• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
• 로드 팩터(Load Factor): 해시 테이블이 얼마나 채워져 있는지를 나타내는 값
  • 로드 팩터 = 저장된 데이터 수 / 슬롯 수
  • 로드 팩터가 너무 높아지면 충돌이 증가하므로, 보통 0.7 이하로 유지
• 리사이징(Resizing): 로드 팩터가 임계치(일반적으로 0.7 이상)를 초과하면 테이블 크기를 늘리고 데이터를 재해싱하는 과정

2. 해쉬 구조

• Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
• 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(value)를 꺼냄
• 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용
• 파이썬에서는 보통 해쉬를 별도로 구현할 이유가 없고 딕셔너리 타입을 사용함

3. 해쉬 테이블의 장단점과 주요 용도

• 장점

  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠름.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

• 단점

  • 일반적으로 저장공간이 좀 더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함

• 주요 용도

  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현 시 (중복 확인이 쉽기 때문)

4. 해시 테이블의 충돌 해결 방법

• 충돌: 서로 다른 키가 동일한 해시 값을 가지는 경우

• 충돌을 해결하기 위한 대표적인 방법

  1. Chaining 기법

     • 개방 해싱(Open Hashing) 기법 중 하나
     • 충돌이 일어나면, 링크드 리스트로 데이터를 추가로 연결하여 저장

Chaining 예제

hash_table = [[] for _ in range(10)]

def insert(key, value):
index = hash(key) % len(hash_table)
hash_table[index].append((key, value))

def get(key):
index = hash(key) % len(hash_table)
for k, v in hash_table[index]:
if k == key:
return v
return None

2. Linear Probing 기법

   • 닫힌 해싱(Close Hashing) 기법
   • 충돌이 발생하면, 해당 해시 주소의 다음 주소부터 빈 공간을 탐색

Linear Probing 예제

def **init**(self, size):
self.size = size
self.table = [None] \* size

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

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

        # 충돌 시 다음 슬롯 탐색
        while self.table[index] is not None:
            index = (index + 1) % self.size

        self.table[index] = (key, value)

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

        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size

        return None

# 테스트

hash_table = LinearProbingHashTable(5)
hash_table.insert(10, "value1")
hash_table.insert(15, "value2") # 충돌 발생
print(hash_table.get(10)) # 출력: value1
print(hash_table.get(15)) # 출력: value2

3. Quadratic Probing (제곱 탐사)

   • 선형 탐사의 단점을 보완해 점프 간격을 제곱 형태로 늘림

4. Double Hashing (이중 해싱)

   • 2개의 다른 해싱 함수를 사용해 새로운 슬롯을 계산

5. 시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
• 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1) 이라고 말할 수 있음

6. 검색에서 해쉬 테이블의 사용 예

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
• 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

7. 파이썬의 해시 테이블

• 파이썬의 딕셔너리(dict)와 집합(set)은 해시 테이블 기반으로 동작.

딕셔너리 사용 예시

hash_table = {}
hash_table["name"] = "Alice"
hash_table["age"] = 25
print(hash_table["name"])  # 출력: Alice

집합 사용 예시

unique_nums = set([1, 2, 2, 3])
print(unique_nums)  # 출력: {1, 2, 3}