간략한 요약
이 강의에서는 해싱에 대해 다루며, 특히 집합 데이터 구조에서 검색, 삽입, 삭제 연산을 최적화하는 방법을 설명합니다. 비교 모델에서의 검색 하한을 증명하고, 직접 접근 배열의 한계를 극복하기 위해 해시 함수와 체이닝을 도입합니다. 무작위 해시 함수를 사용하여 입력에 독립적인 성능을 보장하고, 체인의 길이를 일정하게 유지하는 방법을 제시합니다.
- 비교 모델에서 검색의 하한은 log n이며, 더 빠른 검색을 위해 RAM 모델의 무작위 접근을 활용합니다.
- 직접 접근 배열은 상수 시간 검색을 제공하지만, 큰 키 공간에서는 공간 효율성이 떨어집니다.
- 해시 함수와 체이닝을 통해 공간 효율성을 높이고, 충돌을 관리합니다.
- 보편적 해시 함수를 사용하여 체인의 길이를 일정하게 유지하고, 동적 해싱을 통해 크기 변화에 대응합니다.
소개
이 강의에서는 해싱에 대해 설명하며, 집합 데이터 구조에서 키를 기반으로 항목을 쿼리하는 방법을 다룹니다. 지난 강의에서 다룬 정렬되지 않은 배열과 이진 검색 트리를 사용하여 집합 인터페이스를 구현하는 방법을 복습하고, 검색 연산의 성능을 향상시키는 방법을 모색합니다. 특히, 비교 모델에서의 검색 하한을 증명하고, 이를 극복하기 위한 해싱 기술을 소개합니다.
비교 모델에서의 검색 하한
비교 모델에서는 항목을 블랙 박스로 취급하며, 키를 비교하는 연산만을 사용하여 항목을 구별합니다. 이 모델에서 검색 알고리즘은 결정 트리로 표현될 수 있으며, 각 내부 노드는 비교 연산을 나타내고, 각 리프 노드는 출력을 나타냅니다. n개의 항목을 저장하는 경우, 정확한 검색 알고리즘은 최소 n+1개의 리프 노드를 가져야 하며, 이진 트리의 최소 높이는 log n입니다. 따라서 비교 모델에서 검색의 하한은 log n입니다.
직접 접근 배열
비교 모델의 제약을 극복하기 위해 RAM 모델의 무작위 접근을 활용합니다. 직접 접근 배열은 키를 배열의 인덱스로 사용하여 항목을 저장하며, 상수 시간 검색, 삽입, 삭제를 제공합니다. 그러나 키 공간이 큰 경우, 배열의 크기가 매우 커져 공간 효율성이 떨어지는 문제가 있습니다. u를 저장할 수 있는 가장 큰 키라고 할 때, 직접 접근 배열은 u 크기의 공간을 필요로 합니다.
해시 함수와 체이닝
직접 접근 배열의 공간 문제를 해결하기 위해 해시 함수를 사용하여 큰 키 공간을 작은 공간으로 매핑합니다. 해시 함수는 키를 해시 테이블의 인덱스로 변환하며, 이 과정에서 충돌이 발생할 수 있습니다. 충돌을 해결하기 위해 체이닝 기법을 사용하며, 각 인덱스에 연결 리스트 또는 동적 배열과 같은 추가 데이터 구조를 저장합니다. 이를 통해 여러 항목이 동일한 인덱스에 매핑될 수 있습니다.
보편적 해시 함수
고정된 해시 함수는 특정 입력에 대해 성능이 저하될 수 있으므로, 무작위 해시 함수를 사용하여 입력에 독립적인 성능을 보장합니다. 보편적 해시 함수는 해시 함수족에서 무작위로 선택되며, 임의의 두 키가 충돌할 확률이 1/m 이하입니다. 여기서 m은 해시 테이블의 크기입니다. 보편적 해시 함수를 사용하면 체인의 길이를 일정하게 유지할 수 있으며, 검색, 삽입, 삭제 연산의 기대 시간 복잡도를 상수 시간으로 만들 수 있습니다.
체인 길이 분석
보편적 해시 함수를 사용할 때 체인의 기대 길이를 분석하기 위해 지시 확률 변수를 도입합니다. xij는 키 i와 키 j가 충돌하면 1, 그렇지 않으면 0입니다. 체인 i의 크기는 모든 j에 대한 xij의 합으로 표현될 수 있으며, 체인의 기대 길이는 1 + (n-1)/m으로 계산됩니다. 여기서 n은 저장된 키의 수입니다. m이 n에 비례하면 체인의 기대 길이는 상수 시간이 됩니다.
동적 해싱
해시 테이블에 저장된 항목 수가 증가함에 따라 해시 테이블의 크기를 동적으로 조정해야 합니다. 항목 수가 너무 많아지면 해시 테이블을 재구축하여 m을 늘리고, 체인의 길이를 일정하게 유지합니다. 이를 통해 해시 테이블의 성능을 유지하면서 크기 변화에 대응할 수 있습니다.
