유니버설 해싱

무언가를 고를 때 랜덤으로 고르는게 차라리 최악은 피한다라는 재밌는 논함이 있어서 글을 쓰게 되었다. 우리는 해쉬 테이블을 이용 한다면 해쉬 함수를 당연하게 고려해야하는데, 이 유니버설 해싱이 저점 성능으로 가진 않도록 할 수 있다고 한다.

---

 

해쉬 테이블을 만들 때 해쉬 함수 하나를 매핑해야하는데, 이것을 테이블마다 다르게 할당 시킨다.

이렇게 하면 최악의 시간 복잡도를 피하면서 해쉬 함수 어뷰징을 피할 수 있다.

나쁜 사용자들은 해쉬 함수의 내용을 알아낸다음 거기에 충돌을 계속 일으켜서 성능을 일부러 저하 시킬 수 있었다. 제로 이런 사건이 일어난 이후 PHP에서의 해쉬 테이블을 이용 할 때는 유니버설 해싱 개념의 해쉬 함수를 제공한다.

파이썬도 Dictionary 자료 구조에 랜덤 시드 개념을 적용해오고 있다. 완벽히 같진 않지만, 인터프리터 실행 때마다 시드가 바뀌기 때문에 유니버설 해싱의 개념을 충분히 이용하고 있다.

 

 

예를 들어서, 정수로 구성되는 키 값에 대해 이런 해쉬 함수를 생각 해 볼 수 있다.

return ((randomVal1 * key + ranbomVal2);

그럼 여기서 randomVal1 그리고 randomVal2 를 테이블을 생성하는 매 번 난수로 결정을 하는 것이다.

사실 보장한다기엔 또 혹시나 모르지만, 이 둘 값을 random하게 사용하지 않는 것과 비교하면, 최악의 상황이 발생할 확률을 줄인다고 기대하는 것이 더 옳다. 충돌을 잦게 일으 킬 수 있는 쌍의 값을 확률적으로 피하는 것이다.

 

테이블 생성 때마다 함수 내용이 달라지는 것이다. 만약 레코드 단위로 바뀌었다면 레코드를 찾아갈 방법을 찾는데 시간을 더 썼을 것이다!!