Skip to content

Latest commit

 

History

History
36 lines (23 loc) · 918 Bytes

hash.md

File metadata and controls

36 lines (23 loc) · 918 Bytes

해시 테이블

해시 테이블(Hash Table)은 값을 키로 빠르게 찾기 위한 자료구조입니다.

파이썬에서는 보통 dict와 set으로 사용합니다.

핵심 생각

  • 값을 직접 순회하지 않고, 키로 바로 접근한다.
  • 평균적으로 조회와 갱신이 빠르다.

언제 떠올리면 좋은가

  • 어떤 값이 이미 있는지 빠르게 확인할 때
  • 값별 개수를 셀 때
  • 중복 제거가 필요할 때

파이썬 구현 포인트

d = {}  # -> 빈 dict
d[x] = d.get(x, 0) + 1  # -> 빈도수 증가

s = set()  # -> 빈 set
s.add(x)  # -> 값 추가
x in s  # -> 포함 여부 확인

실수하기 쉬운 것

  • 순서가 항상 의미 있다고 착각하는 것
  • 없는 키를 바로 조회해서 KeyError가 나는 것

기억할 문장

  • 값 존재 여부나 빈도수가 중요하면 해시 테이블을 먼저 떠올린다.