[Python] 해시 테이블 (Hash Table)

Hash Table

 

해시 테이블(Hash Table)은 데이터를 빠르게 저장하고 검색할 수 있는 자료구조입니다.

기본적인 아이디어는 데이터를 배열의 인덱스에 매핑하여 검색 시간을 최소화하는 것입니다.

이 구조는 특히 데이터가 많을 때 매우 효율적입니다.

 

해시 테이블은 키(Key)를 값(Value)에 매핑할 수 있는 구조로 구성되어 있습니다.

 

키(Key) : 데이터를 구분하는 고유한 값
값(Value) : 키에 해당하는 실제 데이터

 

 

 

 

키를 해시 함수를 통해 인덱스로 변환하고, 그 인덱스에 해당하는 위치에 값을 저장합니다.

 

해시 함수 (Hash Function)

 

해시 함수란 입력된 키를 해시 테이블의 인덱스로 변환하는 함수입니다.

해시 함수는 다음과 같은 특성을 가져야 합니다.

 

충돌 최소화 : 서로 다른 키가 같은 인덱스를 갖지 않도록 해야 합니다.

빠른 계산 : 계산 속도가 빨라야 실시간으로 빠르게 키를 변환할 수 있습니다.

 

해시 함수의 특징

 

- 결정성 (Deterministic)
- 고정된 출력 크기 (Fixed Output Size)
- 빠른 계산 (Fast Computation)
- 균일한 분포 (Uniform Distribution)
- 충돌 저항성 (Collision Resistance)

 

 

Hash Table 장점

 

- 빠른 검색 시간 : 평균적으로 O(1) 시간 복잡도로 데이터를 검색할 수 있습니다.

- 빠른 삽입 및 삭제 : 해시 테이블은 데이터 삽입과 삭제가 매우 빠릅니다.

 

Hash Table 단점

 

- 해시 함수의 품질 : 해시 함수가 좋지 않으면 충돌이 많이 발생하여 성능이 저하됩니다.

- 메모리 사용 : 해시 테이블은 일반적으로 더 많은 메모리를 필요로 할 수 있습니다.

- 동적 크기 조정 : 테이블이 꽉 차면 크기를 늘려야 하기 때문에 리사이징 비용이 발생할 수 있습니다.

 

충돌 관리 (Collision Handling)

 

- 해시 함수는 서로 다른 두 키가 동일한 해시 값을 반환하면 충돌합니다.

- 체이닝 (Chaining) : 배열의 각 인덱스에 충돌된 모든 요소를 저장합니다.

- 오픈 주소법 (Open Addressing) : 충돌이 발생하면 다른 빈 슬롯을 찾아 값을 저장합니다. (선형 탐사, 제곱 탐, 이중 해싱 등)

 

해시함수 예시 코드

 

def simple_hash(key, table_size):
    # key의 각 문자(또는 숫자)의 ASCII 값을 더한 후, 테이블 크기로 나눈 나머지를 반환
    hash_value = sum(ord(char) for char in key)  # key의 각 문자의 ASCII 값을 더함
    return hash_value % table_size  # 테이블 크기로 나눈 나머지 값이 해시값

# 해시 테이블 크기 설정
table_size = 10

# 예시 키들
keys = ["apple", "banana", "orange", "grape", "melon"]

# 해시 테이블 생성 (빈 값으로 초기화)
hash_table = [[] for _ in range(table_size)]  # 체이닝 방식 사용

# 키들을 해시 테이블에 삽입
for key in keys:
    hash_index = simple_hash(key, table_size)  # 해시값 계산
    hash_table[hash_index].append(key)  # 해당 인덱스에 키 삽입

# 해시 테이블 출력
for index, bucket in enumerate(hash_table):
    print(f"Index {index}: {bucket}")

 

해시 테이블 Python 예시 코드

 

# 해시 테이블을 Python 딕셔너리로 구현한 예시
hash_table = {}

# 데이터 삽입
hash_table['apple'] = 10
hash_table['banana'] = 20

# 데이터 조회
print(hash_table['apple'])  # 출력: 10
print(hash_table['banana'])  # 출력: 20

# 데이터 삭제
del hash_table['apple']