자료구조 - 해시(Hash Table)

해시(Hash Table)란?

해시 테이블(Hash Table)은 데이터를 키(key)와 값(value)의 쌍으로 저장하는 자료구조입니다.

검색, 삽입, 삭제가 평균적으로 O(1)의 시간복잡도를 가지기 때문에 매우 빠른 연산이 가능한 것이 특징입니다.

왜 해시를 사용할까?

• 빠르게 데이터를 찾고 싶을 때 (ex. 전화번호부, 사전)
• 특정 키를 기반으로 데이터를 효율적으로 저장/관리하고 싶을 때

해시 테이블의 동작 원리

1. 키(key)를 입력받습니다.
2. 해시 함수(hash function)를 사용하여 키를 숫자로 변환합니다.
3. 그 숫자를 배열의 인덱스(index)로 사용하여 값을 저장하거나 꺼냅니다.

예시

hash("apple") → 42  # 해시 함수 결과

→ arr[42] = "apple과 관련된 데이터"

해시 함수란?

해시 함수는 키를 숫자로 바꿔주는 함수입니다.

• 같은 키는 항상 같은 결과를 반환해야 합니다.
• 결과값은 배열의 크기 범위 내여야 합니다.
• 효율적인 해시 함수는 충돌이 적고 고르게 분포됩니다.

충돌(Collision)이란?

두 개의 다른 키가 같은 인덱스로 해시되는 경우를 말합니다.

충돌 해결 방법

방법	설명
체이닝(Chaining)	같은 인덱스에 여러 값을 연결 리스트로 저장
개방 주소법(Open Addressing)	충돌 시 다음 빈 공간에 저장 (선형 탐사 등)

해시 예시 (Python)

파이썬의 dict 자료형은 해시 테이블로 구현되어 있습니다.

phone_book = {}

# 삽입
phone_book["Alice"] = "010-1234-5678"
phone_book["Bob"] = "010-9876-5432"

# 검색
print(phone_book["Alice"])  # 출력: 010-1234-5678

# 삭제
del phone_book["Bob"]

해시 테이블의 시간복잡도

연산	평균 시간복잡도	최악의 경우	설명
검색	O(1)	O(n)	충돌이 많을 경우 O(n)까지 느려질 수 있음
삽입	O(1)	O(n)
삭제	O(1)	O(n)

해시의 장점과 단점

장점

• 평균적으로 매우 빠른 연산 속도 (O(1))
• 키 기반으로 직관적이고 유연한 데이터 저장 가능

단점

• 해시 함수가 좋지 않으면 성능이 급격히 저하됨
• 메모리를 많이 사용할 수 있음
• 데이터가 정렬되지 않음 (순회가 필요할 경우 비효율적)

해시 활용 예시

활용 분야	설명
사전(Dictionary)	단어를 키로 하여 정의를 빠르게 검색
캐시(Cache) 시스템	최근 사용 데이터를 빠르게 저장/검색
중복 체크	데이터셋 내에서 중복 여부를 빠르게 판단
집합(Set) 구현	중복 없는 요소 저장 및 빠른 포함 여부 판단

실생활 비유로 이해하기

🗂️ 해시 테이블은 서랍장이 있는 사무실 캐비닛과 같습니다. 각각의 키(예: 성 이름)는 특정 서랍 번호(해시값)로 변환되어, 그 서랍을 열면 해당 사람의 정보가 저장되어 있는 구조입니다.

정리

항목	해시 테이블
구조	키-값 쌍 저장
주요 연산	삽입, 검색, 삭제
시간복잡도	평균 O(1), 최악 O(n)
충돌 해결 방식	체이닝, 개방 주소법 등
활용 예시	사전, 캐시, 중복 검사 등