[CS기초] 해시 테이블(Hash Table)

해시 테이블 개요

해시 테이블(Hash Table)은 키(Key)에 대응되는 값(Value)을 저장하는 자료구조이다. 해시 함수를 통해 키를 해시 값으로 변환한 뒤, 해시 값에 대응되는 인덱스 위치에 데이터를 저장하여 관리한다.

데이터의 키 값이 변환된 인덱스의 공간에 데이터가 저장된다

 

 

해시 테이블의 특징

삽입, 삭제, 검색, 갱신 모두 평균적으로 O(1) 시간이 소요된다

• 단, 서로 다른 키가 같은 해시 값으로 변환되어 동일한 저장공간에 할당될 경우 충돌(Collision)이 발생하며, 이 충돌이 많아질수록 성능이 저하된다
• 최악의 경우, 모든 키가 동일한 해시 값을 가져 시간 복잡도가 O(N)으로 저하될 수 있다
• 따라서 해시 함수는 각 키가 테이블 전반에 고르게 분포되도록 적절히 설계해야 성능을 최적화할 수 있다

 

충돌 처리(Collision Resolution) 방법

Chaining

• 해시 테이블의 각 인덱스마다 연결 리스트(Linked List)를 구성하여 충돌이 발생하면 리스트의 뒤에 추가로 데이터를 삽입하는 방식이다.
• 구현이 간단하고 충돌 처리에 효과적이다.

Open Addressing

• 충돌이 발생하면 해시 테이블의 다른 빈 공간을 찾아 데이터를 삽입하는 방식이다.
• 위의 방식으로 빈 공간이 채워지면 데이터가 뭉쳐있는 영역이 생기게 되는데 이를 클러스터(Cluster)라 한다. 또 클러스터가 커지면 탐색 범위가 증가하여 성능이 저하되는데, 이를 클러스터링(Clustering)이라 한다.
• 빈 공간을 찾는 방법으로는 주로 다음과 같은 방식이 사용된다.
  • 선형 탐색(Linear Probing)
    • 충돌 시 바로 다음 칸부터 한 칸씩 순차적으로 탐색하여 빈 자리를 찾는다.
    • 유사한 데이터가 붙어있어 캐시 적중률은 높지만 클러스터링이 빈번히 발생할 수 있다
  • 이차 탐색(Quadratic Probing)
    • 충돌 시 원래 위치에서 1칸, 4칸, 9칸 등 거리를 제곱 수로 늘려가며 빈 공간을 찾는다.
    • 클러스터링 현상이 감소하지만, 캐시 적중률은 선형 탐색에 비해 낮아진다.
  • 이중 해싱(Double Hashing)
    • 충돌이 발생했을 때, 두 번째 해시 함수를 통해 이동할 거리를 계산하여 전혀 다른 위치로 이동한다.
    • 클러스터링을 효과적으로 방지하지만, 캐시 적중률은 상대적으로 낮다.

 

 

파이썬에서 해시 테이블의 구현

파이썬에서는 내장 자료구조인 딕셔너리(Dictionary)를 통해 해시 테이블을 간편하게 구현할 수 있다.

# 딕셔너리 생성
hash_table = {}

# 새 키-값 요소 삽입 - 테이블명["키"] = 값
hash_table["apple"] = 5
hash_table["banana"] = 3

# 기존 키-값 요소 삭제 - del 테이블명["키"]
# 단, 삭제할 키가 없는 경우 KeyError가 발생하므로 주의
del hash_table["banana"]

# 키-값 요소가 존재하는지 여부 판단
key = "apple"
if key in hash_table:
    print("사과가 있습니다. 개수 : ", hash_table[key])
else:
    print("사과가 없습니다.")
    
# 기존 키-값 요소 갱신 - 기존 키의 값을 덮어씌우는 방식으로 갱신
hash_table["apple"] = 10

# 모든 키와 값 활용
keys = list(hash_table.keys())     # 모든 키
values = list(hash_table.values()) # 모든 값
items = list(hash_table.items())   # 모든 키-값 쌍