해시 테이블 (Hash Table)

해시 테이블이란?

• Key를 해시 함수에 넣어 고유한 인덱스를 생성하고, 그 인덱스에 데이터를 저장하는 구조
• Key-Value 쌍으로 데이터를 저장
• 빠른 탐색, 삽입, 삭제 가능
• 파이썬에서는 dict, C에서는 배열 + 해시 함수 직접 구현

---

주요 특징

• 평균 시간 복잡도는 O(1)
• Key 값은 변경 불가능한 자료형만 사용 가능 (str, int, tuple 등)
• 해시 충돌이 발생할 수 있으며 이를 처리하는 로직이 필요함

---

언제 사용되는가?

상황	설명
빠른 탐색이 필요할 때	배열보다 훨씬 빠르게 값 조회 가능
키 기반 매핑이 필요할 때	사용자 ID → 정보, 상품명 → 가격 등
중복 체크	등장 여부 확인, 카운팅
실전 문제 대부분	문자열, 배열 문제에 자주 등장

---

자료구조 동작 방식

1. Key에 해시 함수를 적용하여 index 계산
2. 해당 index에 Value 저장
3. 같은 index가 겹치면 충돌 발생 → 별도 충돌 처리 필요

---

해시 테이블 구현 예제

기본 사용

my_dict = {}
my_dict['apple'] = 3
print(my_dict['apple'])   # 3
my_dict['apple'] = 5       # 값 수정
del my_dict['apple']       # 값 삭제

존재 여부 확인

if 'banana' in my_dict:
    print("존재함")

문자 빈도수 세기

s = "banana"
count = {}
for c in s:
    count[c] = count.get(c, 0) + 1

# 결과: {'b': 1, 'a': 3, 'n': 2}

---

시간 복잡도

연산	평균	최악 (충돌 심할 때)
삽입	O(1)	O(N)
탐색	O(1)	O(N)
삭제	O(1)	O(N)

※ 일반적으로 충돌은 잘 발생하지 않도록 구현

---

실전 문제 유형 예시

문제 유형	설명
등장 횟수 세기	문자열, 숫자 빈도수 계산
중복 체크	이미 등장한 값 빠르게 확인
두 수의 합	값과 차이를 저장 후 바로 비교
애너그램 판별	두 문자열의 문자 빈도 비교
스트링 매핑 문제	문자열 → 정수 변환, 좌표 압축 등

---

C언어 구현 시 고려사항

항목	설명
해시 함수	직접 설계 필요 (djb2, BKDR, mod 기반 등)
충돌 처리	체이닝(연결 리스트) 또는 오픈 주소 방식
Key 관리	구조체 + 포인터 조합으로 직접 구현
문자열 비교	strcmp 등 문자열 비교 함수 필요
메모리 해제	사용 후 free 처리 필수

---

관련 파이썬 함수

함수	설명
dict()	딕셔너리 생성
in	키 존재 여부 확인
get(key, default)	키가 없을 경우 기본값 반환
keys() / values()	키 / 값 목록 조회
collections.defaultdict	기본값을 갖는 딕셔너리 생성

---

핵심 요약

• 해시 테이블은 O(1) 성능의 탐색/저장 구조로, 알고리즘에서 거의 필수
• 파이썬은 dict로 매우 간단하게 사용 가능
• 실전에서는 빈도수 세기, 중복 확인, 매핑 등에서 자주 등장
• C에서는 해시 함수, 충돌 처리, 메모리 관리까지 전부 직접 구현해야 함