해시 테이블

백준 예제 문제: https://velog.io/@arin_0303/1920%EB%B2%88

해시 테이블이란?

Key와 Value를 한 쌍으로 저장하는 자료구조입니다. 파이썬의 딕셔너리(dict)가 바로 해시 테이블을 기반으로 구현되어 있습니다.

해시 테이블은 내부적으로 해시 함수(Hash Function)를 사용하여 Key를 고유한 숫자(해시 값)로 변환하고, 이 값을 인덱스로 삼아 Value를 저장합니다. 덕분에 데이터를 매우 빠르게 찾을 수 있습니다.

장점

• 데이터를 찾고, 추가하고, 삭제하는 속도가 매우 빠릅니다. (평균 시간 복잡도: O(1))

• Key와 Value라는 직관적인 구조로 데이터를 관리하기 용이합니다.

• Key에는 다양한 데이터 타입을 사용할 수 있습니다.

단점
해시 충돌(Hash Collision)이 발생할 수 있습니다. 서로 다른 Key가 해시 함수를 거쳐 같은 값을 가리키는 경우인데, 이 경우 탐색 성능이 저하될 수 있습니다. (최악의 경우: O(n))

언제 사용할까?

• 특정 Key(주로 문자열)를 통해 연관된 값을 빠르게 찾아야 할 때 (ex: 이름으로 전화번호 찾기)

• 각 항목의 등장 횟수를 세야 할 때

"apple"에서 각 알파벳의 등장 횟수 세기

# "apple"에서 각 알파벳의 등장 횟수 세기
word = "apple"
counter = {}

for char in word:
    # get(key, 0)은 key가 없으면 0을 반환하라는 의미
    counter[char] = counter.get(char, 0) + 1

print(counter)
# 출력: {'a': 1, 'p': 2, 'l': 1, 'e': 1}

주요 함수 및 사용법 (Python Dictionary 기준)

• 값 추가/수정(Put)

my_dict = {}
my_dict["A"] = True # "A"라는 Key에 True 값을 저장
print(my_dict) # {'A': true}

• 값 조회(Get)

#1. 일반적인 조회(key가 없으면 에러 발생)
value = my_dict["A"]
value = my_dict["B"] # B가 없으므로 에러 발생

#2. 안전한 조회(get)
# Key 'A'가 있으면 해당 Value를, 없으면 기본값(Default)을 반환
value_a = my_dict.get("A", False) # Key 'A'가 있으므로 True 반환
value_b = my_dict.get("B", False) # Key 'B'가 없으므로 False 반환
print(f"A의 값: {value_a}, B의 값: {value_b}") # A의 값: True, B의 값: False

Q1) 해시, 해시 테이블, 해시 맵의 차이?

-해시: 해시함수를 통해 나오는 결과값 자체

-해시 테이블: ‘키-값’ 자료구조 자체

-해시 맵: 프로그래밍에서 ‘키-값’형태의 데이터 타입

Q2) 왜 순서를 보장하지 않나요?
데이터를 0번, 1번, 2번... 순서대로 저장하는 것이 아니라, 해시 함수가 계산해낸 '해시 값'에 따라 정해진 위치에 데이터를 저장하기 때문입니다. 입력된 순서와는 전혀 상관없이 해시 값에 따라 위치가 결정되므로 순서가 뒤죽박죽 섞이게 됩니다.

참고: Python 3.7 버전부터는 딕셔너리가 입력된 순서를 기억하도록 개선되었습니다. 하지만 Set은 여전히 순서는 보장하지 않습니다.

백준 1920번 문제는 결국 'N개의 숫자 중에 M개의 숫자들이 각각 존재하는가?'를 빠르게 확인하는 문제입니다. 따라서 중복을 신경 쓸 필요 없고 존재 여부만 O(1)로 확인하면 되므로, Set을 사용하는 것이 가장 파이썬답고 효율적인 풀이라고 할 수 있습니다.