완벽한 해싱 & 유니버설 해싱

 

완벽한 해싱

 

n개가 n개의 버킷에 하나씩 따로따로 저장된다면 완벽한 해싱이라 볼 수 있다.

입력한 데이터가 뭔지 모두 알고 있을 경우에만 가능하다.

 

대부분의 경우에는 입력이 정확히 어떤 것들이 들어올지

미리 알 수가 없기 때문에 충돌이 최소가 되는 좋은 해시 함수를 사용할 필요가 있다.

 

 

유니버설 해싱

 

유니버설 해싱은 "랜덤 해싱"으로 이해하면 더 쉽다.

난수를 사용하는 무작위 알고리듬이 성능을 높이는 데에 도움이 되는 예로 퀵 정렬을 들 수 있다.

이와 같이 난수의 개념을 해싱 함수에 적용한 것이다.

 

입력이 어떤 것들인지 정확히 알 수 없는 무작위인 경우에 항상 해시값들을 

고르게 분포시켜주는 함수를 만드는 것은 어렵다.

때문에 유니버설 해싱에서는 해시 함수에 난수를 적용한다.

 

 

암호화 해시 함수

 

다양한 길이의 입력을 고정된 길이의 해시값으로 변환시켜주는 함수를 의미한다.

해당 기능을 이용하면

해커가 원래 암호가 뭐였는지를 알아내기 위해

해시값이 동일한 입력을 역으로 추정하는 과정을 거처야하는데,

찾아낼 확률이 매우 낮아진다.