해시테이블(HashTable)
- 데이터를 저장하고 검색하기 위한 자료구조중 하나
- 예시) 서랍장 - 특정 슬롯에 정보를 담아 저장한다.
- 파이썬 : 딕셔너리(Dictionary) 타입
해시 테이블 특징
1. 빠른 검색과 삽입
- 해시 함수를 사용하여 데이터를 고유한 해시 코드로 변환하고, 이를 인덱스로 활용하여 데이터를 저장하고 검색
- 데이터의 검색과 삽입 속도가 상수 시간(O(1))에 수행 [빠른 연산 수행 가능]
2. 고유한 키와 해시 코드
- 중복 데이터를 방지하고 데이터 간의 구별을 가능하게 함.
3. 메모리 사용량
- 배열을 기반으로 하기 때문에 메모리 사용이 비교적 적음.
4. 동적 크기 조절
- 동적으로 크기를 조절할 수 있어서 데이터의 삽입과 삭제에 대한 성능 최적화 가능.
5. 순서가 없는 자료구조
- 순서가 있는 배열 자료구조와 달리 순서가 없고, Key를 통해 값(Value)에 접근한다.
파이썬 코드 예시 - 클래스로 dict 자료삽입 구현
HashTable 클래스
- 주어진 크기의 해시 테이블을 생성
- 인덱스 계산: 해시 함수로 나머지 연산을 사용
- 값 삽입 : insert 메서드를 사용
- 이미 해당 슬롯에 값이 있는 경우 충돌이 발생했다는 메시지를 출력
- get 메서드를 사용하여 주어진 키에 해당하는 값을 조회.
class HashTable:
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)
if self.table[index] is None:
self.table[index] = value
else:
print(f"Collision occurred at index {index}.")
def get(self, key):
index = self.hash_function(key)
return self.table[index]
# 예시 사용
hash_table = HashTable(10)
hash_table.insert(28, "Value for K=28")
hash_table.insert(61, "Value for K=61")
hash_table.insert(18, "Value for K=18")
print(hash_table.get(28)) # 출력: Value for K=28
print(hash_table.get(61)) # 출력: Value for K=61
print(hash_table.get(18)) # 출력: Collision occurred at index 8.
동작원리
데이터 저장 및 검색
- 데이터 저장 : 해시 함수로 데이터의 해시 코드를 계산하고 해당 해시 코드에 맞는 인덱스에 데이터를 저장
- 데이터 검색 : 동일한 해시 함수를 사용하여 해시 코드를 계산하고, 해당 인덱스에서 데이터를 찾음.
1. 해시 함수 (Hash Function)
- 데이터를 입력받아 고정된 길이의 해시 값(해시 코드)을 생성
2. 해시 코드 매핑 (Hash Code Mapping)
- 해시 함수를 사용하여 데이터의 해시 코드를 계산하면, 이 해시 코드를 배열의 인덱스로 매핑.
- 인덱스 결정방법: 일반적으로 해시 코드를 배열 크기로 나눈 나머지를 사용함.
해시 함수(hash function)
해시 함수의 중요성
- 데이터의 분배와 충돌을 관리하는 핵심 요소. [ 해시코드를 기반으로 데이터의 저장 위치가 결정됨. ]
- 충돌을 최소화하고 데이터 관리 및 검색 작업에서 효율성을 유지할수 있는 (= 계산이 빠른 ) 함수를 선정.
부적절한 해시 함수
1. 충돌(Collision) 빈도 증가
- 서로 다른 입력들이 같은 해시 값으로 매핑될 확률증가 -> 충돌 발생
2. 불균형한 데이터 분포
- 일부 해시 버킷(bucket)에 데이터가 집중되어 해당 버킷의 성능 저하 및 다른 버킷의 미사용 문제가 발생할 수 있음.
3. 계산 복잡도 증가
- 데이터 삽입 및 검색 작업에 많은 시간이 소요될 수 있음. -> 성능 저하 및 시스템 부하 증가.
4. 데이터의 무결성 유지 곤란
- 충돌 발생 시 충돌을 효과적으로 해결하는 방법이 없거나 어려울 수 있음.
5. 동적 크기 조정 문제
- 동적 크기 조정을 위한 재해싱(rehashing) 작업 -> 비효율적인 해시 테이블의 크기 조정.
6. 해시 함수 의존도
- 해시 함수를 변경해야 할 경우, 이미 저장된 데이터의 모든 해시 값을 다시 계산해야 할 수 있음.
해시 함수 종류
1. Division Method
이 방법은 간단한 해시 함수 중 하나로, 키를 해시 코드로 변환할 때 나머지 연산을 사용합니다. 해시 테이블 크기를 M이라고 할 때, 키를 M으로 나눈 나머지 값을 해시 코드로 사용합니다. 단순하고 빠른 방법이지만 특정한 입력 데이터에 대해 균일한 분포를 보장하지 않을 수 있습니다.
2. Multiplication Method
이 방법은 키를 곱하고 소수를 곱한 결과의 소수 부분을 해시 코드로 사용합니다. 일반적으로 키의 곱셈 결과에서 정수 부분을 추출하거나 비트 연산을 사용하여 해시 코드를 생성합니다. Division Method보다는 더 균일한 분포를 제공할 수 있습니다.
3. Folding Method
Folding Method는 입력 키를 여러 부분으로 나누고 이들 부분을 더하거나 XOR 연산한 결과를 해시 코드로 사용하는 방법입니다. 이는 긴 입력 키를 해시 코드로 변환할 때 사용되며, 입력 데이터를 더 잘 분산시키는 데 도움을 줄 수 있습니다.
4. 문자열 해시 함수
문자열 해시 함수들은 문자열을 해시 코드로 변환하는 데 사용
- SHA-256 (Secure Hash Algorithm 256)
- 256비트 해시 코드를 생성하는 알고리즘으로, 보안적으로 강력한 해시 함수로 여전히 널리 사용됨.
충돌 해결 (Collision Resolution)
- 서로 다른 데이터가 같은 인덱스에 매핑되는 충돌이 발생할 수 있음.
충돌 해결 기법
개방 주소법(Open Addressing)과 체이닝(Chaining)
- 개방 주소법 : 충돌이 발생하면 다른 빈 슬롯을 찾을 때까지 다음 인덱스를 계속 탐색.
- 체이닝 : 충돌이 발생하면 같은 인덱스에 연결 리스트를 사용하여 데이터를 연결.
