PostsSeriesLabsAlgo

자료구조

해시

사물함을 번호 대신 이름으로 찾기

이름표 여섯 개를 사물함 8칸에 하나씩 넣습니다

규칙 이름의 글자마다 번호가 있습니다 (a=97, b=98 …). 글자 번호를 모두 더하고 8로 나눈 나머지가 그 이름표가 들어갈 칸 번호입니다.

  1. 0빈 칸
  2. 1빈 칸
  3. 2빈 칸
  4. 3빈 칸
  5. 4빈 칸
  6. 5빈 칸
  7. 6빈 칸
  8. 7빈 칸

이름표 1 / 6kim

누른 횟수 0
  • 이름을 번호로 바꿔 칸을 바로 찾아가는 방법 = 해시(hash)
  • 이름을 번호로 바꾸는 규칙 = 해시 함수
  • 두 이름이 같은 칸을 가리키는 일 = 충돌

파이썬의 dict 와 set 이 이 방법을 씁니다. 리스트의 x in arr 은 칸을 처음부터 N 번 훑습니다. set 은 칸 번호를 계산해 바로 엽니다.

리스트에서 in · 1,000,000칸1,000,000칸
set 에서 in · 1,000,000개1칸
맨 끝 값을 찾을 때 열어 보는 칸 수(set 은 평균 한두 칸). 이 컴퓨터에서 직접 재 보니 리스트 약 0.005초, set 약 0.000002초였습니다. 컴퓨터마다 다릅니다.

같은 이름은 언제나 같은 칸이다

  • 규칙이 고정이다 — kim 은 언제 넣어도 1번 칸이다. 그래서 찾을 때도 같은 계산 한 번이면 칸이 나온다
  • 칸 안만 훑는다 — zed 를 찾으려면 3번 칸 하나만 열면 된다. 8칸 전부를 볼 일이 없다
  • 칸 번호가 곧 순서가 아니다 — 먼저 넣었다고 앞 칸에 가지 않는다. kim 은 1번, tom 은 0번이었다
  • 한 칸에 몰리면 느려진다 — 이어 붙은 줄이 길수록 칸 안을 오래 훑는다

코드는 칸을 계산하는 한 줄이 중심이다

다음을 눌러 한 줄씩 넘겨 보세요. 이름표가 칸에 들어가고, 찾을 때는 칸 안만 훑습니다. 위 ① 의 이름표 여섯 개와 같습니다.

  1. 0빈 칸
  2. 1빈 칸
  3. 2빈 칸
  4. 3빈 칸
  5. 4빈 칸
  6. 5빈 칸
  7. 6빈 칸
  8. 7빈 칸

지금 다루는 이름표 없음

다음을 눌러 한 줄씩 넘겨 보세요

filled = 0

build_and_find.py
  1. 1def build_and_find(names, target):
  2. 2 buckets = [[] for _ in range(8)]
  3. 3 for name in names:
  4. 4 slot = sum(ord(c) for c in name) % 8
  5. 5 buckets[slot].append(name)
  6. 6 slot = sum(ord(c) for c in target) % 8
  7. 7 for who in buckets[slot]:
  8. 8 if who == target:
  9. 9 return True
  10. 10 return False
0 / 26
  • sum(ord(c) for c in name) % 8 — 글자 번호를 모두 더해 8로 나눈 나머지 = 칸 번호. ord("a") 는 97
  • buckets[slot].append(name) — 그 칸에 이름표를 이어 붙인다
  • for who in buckets[slot] — 찾을 때는 그 칸 안만 훑는다

진짜 dict 는 글자 합이 아니라 더 잘 섞는 계산을 쓰고, 칸 수도 알아서 늘립니다. 원리는 같습니다.

tom 이 0번 칸에 들어 있습니다. 글자 순서만 다른 mot 을 넣으면 어느 칸으로 갈까요? (m=109, o=111, t=116)

해시에서 틀리는 자리

  • x in 리스트 를 반복문 안에서 — 10만 개에서 맨 끝 값을 2천 번 찾아 보니 리스트 약 1.2초, set 약 0.00007초였다. 반복문 안의 in 은 set 으로 바꾼다
  • 리스트는 키가 못 된다 — {[1, 2]: 1} 은 TypeError(unhashable type: 'list')가 난다. 안의 값이 바뀌면 칸 번호가 달라지기 때문이다. 튜플 (1, 2) 는 된다
  • 칸 번호는 믿지 않는다 — 진짜 hash("kim") % 8 을 두 번 실행해 보니 5 와 3 이 나왔다. 실행할 때마다 값이 다르다
  • dict 순서는 넣은 순서다 — 파이썬 3.7 부터 그렇다. 칸 번호 순서가 아니다
  • 모두 한 칸에 몰리면 — 해시가 전부 0이 되게 만든 키 3천 개를 넣어 보니 약 0.14초, 정상이면 약 0.0004초였다. 평균 한 번이 N 번이 된다

문제에서 이 말이 보이면

있는지 빨리 확인몇 번 나왔는지 세기두 수의 합

두 수의 합은 “짝이 이미 나왔나”를 set 한 번으로 확인합니다. 반복문 안에 in 리스트 가 있으면 set 으로 바꿀 자리입니다.

다음 장에서는 가장 급한 것부터 꺼내는 힙을 봅니다.