충돌 문제와 해결 방법

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} 초")