유니버설 해싱(랜덤 해싱)

완벽한 해싱

n개가 n개의 버킷에 하나씩 따로따로 저장된다면 완벽한(perfect) 해싱이라고 볼 수 있습니다. 입력 데이터가 뭔지를 모두 알고 있을 경우에만 가능합니다. 예를 들어서 입력 키가 "Apple", "Orange", "Kiwi" 3가지라고 고정이 되어있다면 각각 0, 1, 2에 대응시키면 메모리 낭비 없이 O(1)으로 처리할 수 있습니다.

대부분의 경우에는 입력이 정확히 어떤 것들이 들어올지 미리 알 수가 없기 때문에 충돌이 최소가 되는 좋은 해시 함수를 사용할 필요가 있습니다.

 

유니버설 해싱

유니버설 해싱이라는 이름 보다는 "랜덤 해싱"이라는 이름이 더 이해하기 쉬울 것 같습니다. 난수를 사용하는 무작위 알고리듬이 성능을 높이는 데에 도움이 된다는 것은 앞에서 퀵 정렬에서 본 적이 있습니다. 여기서도 해시 함수에 난수를 사용합니다.

입력이 어떤 것들인지 정확히 알 수 없는 무작위인 경우에 항상 해시값들을 고르게 분포시켜주는 함수를 만드는 것은 어렵습니다. 유니버설 해싱에서는 해시 함수에 난수를 사용합니다.

예를 들면, 정수 키에 대해서

return ((a*key + b) % p) % n;

와 같은 형태의 해시 함수를 사용할 수 있습니다. 이때 a와 b는 해시 클래스의 생성자에서 난수로 결정합니다. p는 예상되는 키의 가짓수보다 큰 소수(prime)입니다. n은 버킷의 수 입니다. 예를 들어서, 생일 역설에서 p는 365보다 큰 소수인 367을 사용할 수 있습니다. 입력이 명확하지 않을 경우에는 그냥 큰 소수를 사용하는 경우도 있습니다. a와 b에 난수를 사용하면 a와 b에 고정된 숫자를 사용하는 것과 비교했을 때 최악의 상황이 발생하는 확률을 줄일 수 있다고 "기대"할 수 있습니다. "분할"에서 입력과 피벗의 최악의 조합을 피하는 것과 비슷합니다. 입력 key들에 대해서 충돌을 많이 일이키는 a와 b를 확률적으로 피하는 것입니다.

a와 b를 해시함수를 호출할 때마다 매번 랜덤하게 바꾼다는 얘기는 아니니 오해 없으시길 바랍니다. 해시에 저장할때 사용한 해시함수와 값을 찾거나 바꿀때 사용하는 해시 함수는 같아야 합니다. 해시 클래스를 초기화할때 한 번 랜덤하게 결정한다는 의미입니다. 

증명은 정수론과 소수의 성질을 사용하는데 더 궁금하신 분들은 스탠퍼드 CS161 Lecture8 강의노트 또는 CLRS Theorem 11.4 (p.289)를 참고하세요. mod 식 전개를 이해하기 위해서는 이산수학의 remainder classes도 필요합니다.

 

암호화 해시 함수

다양한 길이의 입력을 고정된 길이의 해시값으로 변환시켜주는 함수를 의미합니다. 예를 들어서, SHA256이라는 NIST 표준 암호화 해시 함수는 긴 문장이나 이미지 등도 256bit(320byte)의 해시값으로 변환시켜줍니다. 암호화를 할 때 많이 사용하기 때문에 암호화 해시 함수라고 부릅니다. 예를 들면, 우리의 암호를 서버에 저장할때는 암호 자체가 아니라 암호의 해시값을 저장합니다. 그러면, 서버에서는 암호가 맞았나 틀렸나만 판단할 수 있습니다. 해커가 원래 암호가 뭐였는지를 알아내려면, 해시값이 동일한 입력을 역으로 추정하는 과정을 거쳐야 하는데 찾아낼 확률이 매우 낮습니다.