개념 확인: Open Addressing

1. 원소 9개를 길이 12인 표에 저장했을 때 원소 수를 표 길이로 나눈 load factor α를 구한다.
2. 길이 6인 표에 다음 칸을 차례로 확인하는 linear probing으로 키 8, 14, 20을 넣을 때 각 키가 확인한 인덱스와 저장 인덱스를 적는다.
3. 표 길이를 12로 늘려 같은 순서로 다시 넣을 때 각 키의 저장 인덱스를 적는다.
4. 기존 배열 위치를 그대로 복사하지 않고 모든 키를 다시 넣어야 하는 이유를 적는다.

문제 2~4는 길이 m = 11인 표와 h(k) = k mod 11을 쓴다.

1. 키 12, 23, 34, 9, 20을 차례로 넣을 때 각 키가 확인한 인덱스와 저장 인덱스를 적는다.
2. get(34)와 get(45)가 확인하는 인덱스, 확인한 칸 수, 결과를 적는다.
3. 다른 키가 있는 칸을 만났다는 이유만으로 탐색을 실패로 끝내면 안 되는 이유를 적는다.
4. 클러스터링(clustering)은 활성 칸이 연속된 구간을 이루는 현상이다. 인덱스 1~3의 클러스터링이 이후 삽입에 주는 영향을 설명한다.

문제 2의 표 길이와 해시 함수를 쓴다.

문제 2의 다섯 키를 넣은 표(인덱스 1, 2, 3, 9, 10에 키가 저장되어 있다)에서 시작한다. 1과 2는 각각 따로 생각한다.

1. quadratic probing (h(k) + i²) mod 11로 키 45를 넣을 때 확인한 인덱스와 저장 인덱스를 적는다.
2. double hashing (h₁(k) + i·h₂(k)) mod 11, h₂(k) = 1 + (k mod 5)로 키 56을 넣을 때 h₂(56), 확인한 인덱스, 저장 인덱스를 적는다.
3. h₂(k)가 0이 되면 안 되는 이유를 적는다.
4. linear probing과 비교해 double hashing이 같은 시작 인덱스를 가진 키들에 대해 달라지는 점을 적는다.

문제 2의 표 길이와 해시 함수를 쓴다.

문제 2의 다섯 키를 넣은 표에서 인덱스 2의 키 23을 삭제한다. tombstone은 지운 자리라는 표시다.

1. 인덱스 2를 처음부터 빈 칸과 같은 상태로 바꾼 뒤 get(34)를 하면 어떤 결과가 나오는지 적는다.
2. 인덱스 2에 tombstone을 남긴 뒤 get(34)가 확인하는 인덱스와 결과를 적는다.
3. tombstone을 남긴 상태에서 키 45를 넣을 때 확인하는 인덱스와 저장 인덱스를 적는다.
4. 삭제 직후 활성 원소 수 n과, 활성 칸과 tombstone을 합한 수 q를 적고 q를 따로 세는 이유를 적는다.

1. (1, 2), "id", [1, 2] 가운데 dict 키로 쓸 수 없는 것과 이유를 적는다.
2. d = {1: "first"} 뒤에 d[1.0] = "updated"를 실행했을 때 len(d)와 d[True]를 적는다.
3. d = {"a": 1, "b": 2, "c": 3}에서 d["b"] = 20을 실행한 뒤와, 이어서 del d["b"] 후 d["b"] = 2를 실행한 뒤의 키 순서를 적는다.
4. dict 탐색이 해시 값이 같은 항목을 찾은 뒤에도 키를 비교하는 이유를 적는다.