Universal Hashing 이해하기

2023. 9. 16. 11:56

Hash Motivation

Direct Access Array

Hashing

Chaining

chaining 은 해쉬 테이블이 아닌 다른 자료 구조에 아이템을 저장해서 충돌을 해결하는 방법입니다. 해쉬 테이블의 각 인덱스에는 아이템이 아닌 또 다른 자료 구조를 가르키는 포인터가 저장됩니다. 이 자료 구조는 insert, search, 그리고 delete(k) 를 상수 비용으로 지원하는 Set Interface 이고 chain 이라고 합니다. linked list 나 array 를 생각하면 됩니다.

충돌이 발생해도 모든 해쉬 테이블의 chain 의 크기가 상수 이면 insert, serach, 그리고 delete(k) 를 O(1) 으로 수행할 수 있게 되고 이것이 hashing 을 통해 달성하고자 하는 목표인데요. 이를 위해서는 해쉬 함수가 중요합니다. 만약에 아주 안좋은 해쉬 함수를 선택해서 모든 키의 해쉬 값이 동일한 인덱스를 가진다면, 해당 인덱스 chain 의 크기는 O(n) 이 되고 insert, serach, 그리고 delete(k) 의 비용도 O(n) 이 되버립니다. 최악이죠.

이상적으로 어떠한 키 유니버스가 주어져도 충돌의 개수를 줄여서 테이블의 가장 큰 chain 의 크기가 상수인 해쉬 함수를 선택해야 합니다.