7.1 해시 테이블에서의 충돌 정의
해시 테이블에서의 충돌은 두 개의 다른 키가 같은 배열 인덱스로 해싱될 때 발생해. 이렇게 되면 두 개 이상의 요소가 같은 해시 테이블 셀을 차지하려고 해.
충돌의 예:
간단한 해시 함수가 테이블 크기에 대한 키의 나머지를 반환한다고 가정해 보자. 테이블 크기가 10일 때 키 5와 15는 동일한 인덱스를 주게 돼: 5 % 10 = 5와 15 % 10 = 5. 이것이 충돌이야.
또 다른 예:
이름 사전을 작성한다고 가정해, 그리고 첫 번째 문자를 반환하는 간단한 해시 함수를 가지고 있어. 근데 이름의 80%가 "A"로 시작하면, 이건 단순한 충돌이 아니라 문제야.
7.2 충돌 해결 방법 – 체이닝
해시 테이블에서 충돌을 해결하는 여러 가지 방법이 있어. 가장 일반적인 두 가지 방법은 체이닝(chaining)과 오픈 어드레싱(open addressing)이야.
체이닝 (Chaining)
장점:
- 구현이 쉽다.
- 충돌이 적은 경우 효율적이다.
- 해시 테이블 밀도에 덜 의존적이다.
단점:
- 연결 리스트의 포인터를 위한 추가 메모리가 필요하다.
- 충돌이 많은 경우 긴 체인으로 인해 성능이 감소할 수 있다.
체이닝 방법 구현 예제:
insert 함수의 작동 방식을 배우기만 하면 되지만, 편의를 위해 전체 코드를 제공할게.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# 사용 예제:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # 출력: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # 출력: None
7.3 두 번째 방법 – 오픈 어드레싱
오픈 어드레싱 방법은 충돌 시 배열의 다음 사용 가능한 셀을 찾는거야. 여러 전략이 있어: 선형 탐사, 제곱 탐사 및 이중 해싱.
장점:
- 포인터 저장을 위한 추가 메모리가 필요 없다.
- 더 컴팩트한 데이터 표현.
단점:
- 테이블 밀도가 높을 때 성능이 크게 떨어질 수 있다.
- 충돌 해결을 위해 더 많은 계산 자원이 필요하다.
오픈 어드레싱 전략 예제
선형 탐사 (Linear Probing):
- 단계가 1인 탐사:
index = (index + 1) % size. - 간단하지만 "클러스터링"을 유발할 수 있다.
제곱 탐사 (Quadratic Probing):
- 단계가 제곱으로 증가하는 탐사:
index = (index + i^2) % size. - 클러스터링 문제를 줄이지만 구현이 더 복잡하다.
이중 해싱 (Double Hashing):
- 두 번째 해시 함수를 사용하여 단계 계산:
index = (index + i * hash2(key)) % size. - 클러스터링 문제가 적지만 구현이 복잡하다.
오픈 어드레싱 방법 구현 예제(선형 탐사): 전체 작동 코드를 제공할 테니 insert 함수의 작동 방식만 파악해도 돼
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
def delete(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = (index + 1) % self.size
if index == original_index:
break
# 사용 예제:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # 출력: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # 출력: None
7.4 충돌이 해시 테이블에 미치는 영향
충돌이 성능에 미치는 영향.
평균 접근 시간:
- 이상적인 조건(충돌이 없는 경우)에서 해시 테이블의 요소에 대한 평균 접근 시간은
O(1)이다. - 충돌이 발생할 경우, 체인을 관리하거나 셀을 탐사해야 하므로 접근 시간이 증가해.
체인의 길이 증가:
- 체이닝 방법에서 충돌이 많을 경우 체인의 길이가 증가하면 검색, 삽입 및 삭제 연산에 대한 접근 시간이
O(n)이 될 수 있어. - 긴 체인은 요소를 찾거나 삽입할 때 필요한 비교 횟수를 증가시킨다.
공간 복잡성:
- 체이닝 방법에서는 연결 리스트의 포인터를 저장하기 위한 추가 메모리가 필요해.
- 오픈 어드레싱 방법에서는 테이블 밀도가 일정 수준(일반적으로 약 70-80%) 이상이 될 때 충돌이 크게 증가하고 이에 따라 접근 시간이 늘어난다.
클러스터링: 오픈 어드레싱 방법(특히 선형 탐사)을 사용할 때 여러 연속된 셀들이 차지되는 클러스터링 현상이 발생하여 충돌 가능성이 증가하고 성능이 저하된다.
충돌이 성능에 미치는 영향 분석 예제:
깊이 파고들고 싶어하는 사람들을 위한 것
import time
import random
# 선형 탐사
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
# 삽입할 데이터 많이 생성하기
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]
# 데이터 삽입 및 시간 측정
start_time = time.time()
for key in keys:
hash_table.insert(key, key)
print(f"삽입 시간: {time.time() - start_time:.6f} 초")
# 데이터 검색 및 시간 측정
start_time = time.time()
for key in keys:
hash_table.search(key)
print(f"검색 시간: {time.time() - start_time:.6f} 초")
GO TO FULL VERSION