6.5 연습 문제¶

6.5.1 개념 확인¶

버킷이 5개인 해시 테이블의 해시 함수는 \(h(x)=x \bmod 5\)다. 충돌이 나면 해당 버킷의 리스트에 원소를 순서대로 넣는다. [1, 6, 11, 7]을 차례대로 삽입한다.

참고 답안

\(1\bmod5=6\bmod5=11\bmod5=1\)이고 \(7\bmod5=2\)이므로 각 버킷의 내용은 다음과 같다.
```
0: []
1: [1, 6, 11]
2: [7]
3: []
4: []
```
6을 찾을 때는 먼저 1번 버킷으로 들어가 1, 6을 차례대로 비교한다. 두 번째 비교에서 목표를 찾는다.
해시값이 같다는 것은 같은 버킷에 들어간다는 뜻일 뿐, 원소들이 같다는 뜻은 아니다. 체이닝은 충돌한 원소를 모두 버킷에 저장하고, 탐색할 때 하나씩 비교한다. 따라서 1, 6, 11은 서로를 덮어쓰지 않는다.

체이닝을 사용하는 해시 테이블에 원래 5개의 버킷이 있고, 해시 함수는 \(h(x)=x\bmod5\)다. 키 [1, 6, 11]은 모두 1번 버킷에 있다.

이제 버킷 수를 7개로 늘리고 해시 함수도 \(h(x)=x\bmod7\)로 바꾼다.

참고 답안

새 버킷 번호는 각각 다음과 같다.
- \(1\bmod7=1\)
- \(6\bmod7=6\)
- \(11\bmod7=4\)
1번 버킷에 1, 4번 버킷에 11, 6번 버킷에 6이 저장된다. 세 키가 더 이상 하나의 버킷에 모여 있지 않다.
그대로 복사해서는 안 된다. 버킷 번호는 키를 버킷 수로 나눈 나머지로 구한다. 버킷 수가 5에서 7로 바뀌면 같은 키의 버킷 번호도 달라질 수 있으므로, 모든 키의 위치를 다시 계산해야 한다. 이전 1번 버킷을 그대로 복사하면 새 식으로 6과 11을 찾을 때 각각 6번 버킷과 4번 버킷으로 가게 되어 찾지 못한다.

해시 테이블에 5개의 자리가 있고 인덱스는 0～4이며, 해시 함수는 \(h(x)=x\bmod5\)다. 충돌이 나면 해시 함수로 계산한 인덱스부터 오른쪽으로 이동하며 처음 만나는 빈자리를 찾는다.

[1, 6, 11]을 차례대로 삽입한다.

세 수는 최종적으로 각각 어느 인덱스에 저장되는가?
11을 찾을 때 어떤 인덱스를 차례대로 확인하는가?
6을 삭제하면서 그 자리를 ‘한 번도 사용하지 않은 빈자리’로 바꾸고, 탐색은 빈자리를 만나면 멈춘다고 하자. 다시 11을 찾으면 어떤 일이 일어나는가? 그 결과는 올바른가? 문제가 있다면 어떻게 피할 수 있는가?

참고 답안

1은 인덱스 1에 저장된다. 6도 인덱스 1로 매핑되지만 충돌하므로 인덱스 2에 저장된다. 11 역시 인덱스 1부터 시작해 이미 사용 중인 인덱스 1과 2를 지나 인덱스 3에 저장된다.
11을 찾을 때는 인덱스 1, 2, 3을 차례대로 확인하고 인덱스 3에서 찾는다.
인덱스 2를 ‘한 번도 사용하지 않음’을 뜻하는 빈자리로 바꾸면, 11을 찾다가 인덱스 1을 확인한 뒤 인덱스 2에서 멈춘다. 따라서 11이 없다고 잘못 판단한다. 삭제할 때는 ‘삭제됨’ 표시를 남겨야 한다. 탐색 중 이 표시를 만나면 다음 인덱스를 계속 확인하고, 인덱스 4를 지나면 0으로 돌아간다. 이후 삽입할 때는 이 자리를 다시 사용할 수 있다.

영어 소문자만 포함하는 두 문자열 s와 t가 주어진다. s의 문자 위치는 자유롭게 바꿀 수 있지만 문자를 추가하거나 삭제하거나 다른 문자로 바꿀 수는 없다.

순서를 바꿔 t를 만들 수 있는지 판단하고, 가능하면 true, 그렇지 않으면 false를 반환하라. 문자열의 문자를 정렬하지 말고 해시 테이블로 각 문자의 등장 횟수를 기록하라.

풀이 힌트