부산대학교자료구조
Scientific Inference Lab

Keys to Indices

Hash Tables and Chaining

키에서 버킷을 계산하고 충돌을 체이닝으로 처리하는 과정을 추적한다.

문제 1

해시 함수로 인덱스 계산하기

  1. 길이 11인 표에서 h(k) = k mod 11일 때 키 93, 17, 44, 60의 인덱스를 구하고 충돌하는 키를 찾는다.
  2. 문자 번호의 단순 합으로 dog과 god의 인덱스를 구한다. ord('d') = 100, ord('o') = 111, ord('g') = 103이다.
  3. 문자 위치 가중치(첫 글자 ×1, 둘째 ×2, 셋째 ×3)를 곱해 더하면 두 문자열의 인덱스가 어떻게 되는지 구한다.
  4. 해시 함수가 빠르면서도 키를 고르게 나누어야 하는 이유를 적는다.
해설 펼치기
  1. 93 mod 11 = 5, 17 mod 11 = 6, 44 mod 11 = 0, 60 mod 11 = 5다. 93과 60이 충돌한다.
  2. 두 문자열 모두 합이 100 + 111 + 103 = 314이고 314 mod 11 = 6이라 같은 인덱스다.
  3. dog은 100×1 + 111×2 + 103×3 = 631, 631 mod 11 = 4다. god은 103×1 + 111×2 + 100×3 = 625, 625 mod 11 = 9다. 순서가 구분된다.
  4. 해시 계산도 탐색 비용에 포함되고, 키가 한 버킷에 몰리면 그 버킷을 비교하는 비용이 커지기 때문이다.
문제 2

체이닝으로 저장하기

길이 m = 7인 체이닝 해시테이블에 h(k) = k mod 7로 키 15, 22, 8, 29, 3을 차례로 저장한다. 같은 버킷에서는 뒤에 붙인다.

  1. 키가 들어 있는 버킷과 각 버킷의 키 순서를 적는다.
  2. get(29)와 get(36)에서 비교하는 키의 수와 결과를 적는다.
  3. 이 표에서 탐색이 느린 원인을 적는다.
  4. 해시 값이 같은 버킷을 찾은 뒤에도 키를 비교해야 하는 이유를 적는다.
해설 펼치기
  1. 15, 22, 8, 29는 모두 나머지가 1이라 버킷 1에 [15, 22, 8, 29], 3은 버킷 3에 [3]이다.
  2. get(29)는 버킷 1의 키를 4번 비교해 찾는다. get(36)은 36 mod 7 = 1이라 버킷 1의 키 4개를 모두 비교한 뒤 실패한다.
  3. 키가 버킷 1에 몰려 버킷 길이가 길어졌다. 이 키들에 h(k) = k mod 7이 고르게 퍼지지 않았다.
  4. 같은 버킷에 서로 다른 키가 함께 있을 수 있으므로 원래 키를 비교해야 원하는 항목을 구분한다.
문제 3

set, get, remove 절차

체이닝 해시테이블에 ("Kim", 90)이 저장되어 있다.

  1. set("Kim", 95)를 호출할 때 세 단계와 결과를 적는다.
  2. remove("Lee")를 호출했는데 해당 버킷에 "Lee"가 없다. 표에 어떤 일이 생기는지 적는다.
  3. 저장과 탐색이 서로 다른 인덱스 계산을 쓰면 생기는 문제를 적는다.
  4. Python dict에서 score["Kim"], "Kim" in score, del score["Kim"]가 각각 어떤 Map 연산에 대응하는지 적는다.
해설 펼치기
  1. h("Kim")으로 버킷을 고르고, 버킷에서 같은 키 "Kim"을 찾은 뒤, 있으므로 값만 95로 바꾼다. 새 쌍을 추가하지 않는다.
  2. 표를 바꾸지 않고 실패를 알린다.
  3. 저장한 키를 다른 버킷에서 찾게 되어 다시 찾을 수 없다.
  4. get(k), contains(k), remove(k)다.
문제 4

버킷 길이와 비용

해시 함수 계산은 O(1)이고 선택된 버킷 길이가 b일 때 탐색 비용은 O(1 + b)다. 항목은 n = 12개다.

  1. 버킷 4개에 키가 고르게 3개씩 퍼졌을 때 한 번의 탐색에서 비교하는 키의 최대 수를 적는다.
  2. 모든 키가 한 버킷에 몰렸을 때의 최대 비교 수와 비용을 적는다.
  3. 버킷 없이 모든 쌍을 리스트 하나에 저장한 LinearMap의 get 최대 비교 수와 비용을 적는다.
  4. 해시테이블의 O(1) 탐색이 모든 입력에서 보장되는 최악 비용이 아닌 이유를 적는다.
해설 펼치기
  1. b = 3이므로 최대 3번이다.
  2. b = 12이므로 12번, O(n)이다.
  3. 12번, O(n)이다.
  4. 키가 고르게 퍼지고 표가 충분히 커서 버킷 길이가 작게 유지될 때에만 O(1)에 가깝다. 한 버킷에 몰리면 O(n)이다.
문제 5

표를 늘리고 다시 넣기

버킷 4개, h(k) = k mod 4인 표에 키 5, 9, 13, 6이 있다.

  1. 현재 각 키의 버킷을 적는다.
  2. 버킷 수를 8로 늘려 h(k) = k mod 8로 다시 넣을 때 각 키의 새 버킷을 적는다.
  3. 기존 버킷 번호를 그대로 복사하면 안 되는 이유를 적는다.
  4. Python hash() 결과를 파일에 저장해 다음 실행에서 식별자로 쓰면 안 되는 이유를 적는다.
해설 펼치기
  1. 5, 9, 13은 버킷 1, 6은 버킷 2다.
  2. 5는 5, 9는 1, 13은 5, 6은 6이다.
  3. 나머지를 구하는 나누는 수가 4에서 8로 바뀌어 같은 키의 인덱스가 달라지므로, 모든 키의 인덱스를 새 표 길이로 다시 계산해야 한다.
  4. hash()는 같은 실행 안에서 같은 키를 같은 버킷으로 보내는 데 쓰는 값이며 영구 식별자로 설계되지 않았다.