6.4 요약¶
1. 핵심 정리¶
- 해시 테이블은
key를 입력받아 \(O(1)\) 시간에value를 조회하므로 매우 효율적이다. - 대표적인 연산에는 조회, 키-값 쌍 추가와 삭제, 해시 테이블 순회 등이 있다.
- 해시 함수는
key를 배열 인덱스로 매핑하여 해당 버킷에 접근하고value를 얻도록 한다. - 서로 다른 두
key가 해시 함수를 거쳐 같은 배열 인덱스를 얻으면 잘못된 조회 결과가 발생할 수 있다. 이를 해시 충돌이라고 한다. - 해시 테이블 용량이 클수록 충돌 확률이 낮으므로 용량 확장으로 충돌을 완화할 수 있다. 배열과 마찬가지로 해시 테이블의 용량 확장 비용도 크다.
- 적재율은 원소 수를 버킷 수로 나눈 값이며, 해시 충돌의 심각도를 반영한다. 용량 확장의 시작 조건으로 자주 사용된다.
- 체이닝은 단일 원소를 연결 리스트로 바꾸어 충돌하는 모든 원소를 같은 리스트에 저장한다. 리스트가 너무 길면 조회 효율이 낮아지므로, 레드-블랙 트리로 바꾸어 효율을 높일 수 있다.
- 개방 주소법은 여러 차례 탐사하여 해시 충돌을 처리한다. 선형 탐사는 고정 간격을 사용하며, 원소를 삭제할 수 없고 군집이 생기기 쉽다는 단점이 있다. 다중 해싱은 여러 해시 함수로 탐사하므로 군집은 덜 생기지만 계산량이 늘어난다.
- 프로그래밍 언어마다 해시 테이블 구현이 다르다. 예를 들어 Java의
HashMap은 체이닝을, Python의dict는 개방 주소법을 사용한다. - 해시 테이블의 해시 알고리즘에는 결정성, 높은 효율, 균등 분포가 필요하다. 암호학에서는 충돌 저항성과 눈사태 효과도 갖추어야 한다.
- 해시 알고리즘은 해시값의 균등 분포를 최대한 보장하고 충돌을 줄이기 위해 보통 큰 소수를 모듈러 연산의 법으로 사용한다.
- 대표적인 해시 알고리즘으로 MD5, SHA-1, SHA-2, SHA-3 등이 있다. MD5는 파일 무결성 검사에, SHA-2는 보안 응용과 프로토콜에 자주 쓰인다.
- 프로그래밍 언어는 보통 자료형별 내장 해시 알고리즘을 제공하여 버킷 인덱스를 계산한다. 일반적으로 불변 객체만 해시 가능하다.
2. Q & A¶
Q: 해시 테이블의 시간 복잡도가 \(O(n)\)이 되는 경우는 언제인가?
해시 충돌이 심하면 시간 복잡도가 \(O(n)\)으로 나빠진다. 해시 함수를 잘 설계하고 용량을 적절히 정하며 충돌이 비교적 고르게 분포하면 \(O(1)\)이다. 프로그래밍 언어의 내장 해시 테이블을 사용할 때는 보통 시간 복잡도를 \(O(1)\)로 본다.
Q: 해시 함수 \(f(x) = x\)를 사용하면 충돌이 없을 텐데, 왜 그렇게 하지 않는가?
\(f(x) = x\)에서는 각 원소에 고유한 버킷 인덱스가 대응하므로 배열과 같다. 그러나 입력 공간은 보통 출력 공간(배열 길이)보다 훨씬 크므로, 해시 함수의 마지막 단계에서 대개 배열 길이로 나눈 나머지를 구한다. 즉, 해시 테이블의 목적은 큰 상태 공간을 작은 공간에 매핑하면서 \(O(1)\)의 조회 효율을 제공하는 것이다.
Q: 해시 테이블도 배열, 연결 리스트, 이진 트리로 구현되는데 어떻게 이들보다 효율이 높을 수 있는가?
첫째, 시간 효율은 높아지지만 공간 효율은 낮아진다. 해시 테이블에는 사용하지 않는 메모리가 상당 부분 있다.
둘째, 특정 활용 상황에서만 시간 효율이 높아진다. 같은 기능을 배열이나 연결 리스트로 같은 시간 복잡도에 구현할 수 있다면 보통 그쪽이 더 빠르다. 해시 함수 계산에 비용이 들어 시간 복잡도의 상수항이 더 크기 때문이다.
마지막으로 해시 테이블의 시간 복잡도도 나빠질 수 있다. 예를 들어 체이닝에서는 연결 리스트나 레드-블랙 트리에서 탐색하므로, 여전히 \(O(n)\) 시간으로 나빠질 위험이 있다.
Q: 다중 해싱도 원소를 곧바로 삭제할 수 없는가? 삭제 표시를 한 공간은 다시 사용할 수 있는가?
다중 해싱은 개방 주소법의 한 종류다. 개방 주소법은 모두 원소를 곧바로 삭제할 수 없으므로 삭제 표시를 해야 한다. 표시된 공간은 다시 사용할 수 있다. 새 원소를 삽입할 때 해시 함수로 삭제 표시가 있는 위치를 찾으면 그곳에 새 원소를 넣을 수 있다. 이렇게 하면 탐사 순서를 유지하면서 공간 활용률도 보장한다.
Q: 선형 탐사에서는 원소를 찾을 때도 왜 해시 충돌이 발생하는가?
해시 함수로 해당 버킷과 키-값 쌍을 찾았는데 key가 일치하지 않으면 해시 충돌이 있다는 뜻이다. 따라서 미리 정한 간격으로 뒤를 차례로 탐색하다가 올바른 키-값 쌍을 찾거나, 찾을 수 없다고 판단하면 종료한다.
Q: 해시 테이블의 용량 확장은 왜 해시 충돌을 완화하는가?
해시 함수는 마지막에 대개 배열 길이 \(n\)으로 나눈 나머지를 구하여 출력이 인덱스 범위에 들어가도록 한다. 용량을 늘리면 \(n\)이 바뀌고 key에 대응하는 인덱스도 달라질 수 있다. 원래 같은 버킷에 있던 여러 key가 여러 버킷으로 분산될 수 있으므로 충돌이 완화된다.
Q: 효율적으로 저장하고 접근하려는 목적이라면 배열을 바로 사용하면 되지 않는가?
key가 좁은 범위의 연속된 정수라면 배열을 바로 쓰는 것이 간단하고 효율적이다. 하지만 문자열처럼 다른 자료형이면 해시 함수로 key를 배열 인덱스에 매핑하고 버킷 배열에 원소를 저장해야 한다. 이것이 바로 해시 테이블이다.