What is a good Hash Function?

좋은 Hash Function이란 무엇일까요? 아마도 Hash Table이 좋은 성능을 가지도록 하는 함수라고 볼 수 있을 것 같습니다.

그러면 Hash Function이 어떻게 Hash Table의 성능을 향상시킬 수 있을까요?

Time to get Hash code

먼저 Hash code를 도출해내는 속도를 생각해볼 수 있습니다.

결국 Hash Table을 사용하는 이유는 저장되어 있는 Data로 빠르게 접근하고자 하는 것입니다.

이 과정에서 Hash Function이 너무 많은 시간을 소모한다면 전체적인 Hash Table의 성능에 악영향을 줄 것입니다.

Collision

하나의 bin에 너무 많은 Data들이 저장된다면 이 또한 Hash Table의 성능을 낮추는 요인이 될 것입니다.

예를 들어 10개의 data와 10개의 bins가 존재한다고 가정해보겠습니다.

만약 10개의 bins에 1개씩 data가 들어간다면, 10개의 data 모두에 접근하는 데 필요한 탐색 수는 10으로 생각할 수 있습니다.

그런데 만약 1개의 bin에 data 10개가 모두 들어있다면 어떻게 될까요?

맨 앞에 있는 data는 1번의 탐색으로 끝나지만 두 번째 data는 2번, 세 번째 data는 3번, ... 총 10 * (10 + 1) / 2 = 55 만큼의 탐색이 필요해집니다.

등차수열의 합 : n * (n + 1) / 2

Uniformity

위와 같이 Hash Table의 Data를 좀 더 빠르게 탐색하기 위해서는 최대한 Data들을 여러 bins에 골고루 분배해야 한다는 것을 알 수 있습니다.

즉 Hash Function의 결과를 토대로 얻어낸 Index의 분포가 Uniform Distribution을 나타내는 것이 이상적인 상황인 것으로 생각할 수 있습니다.

이러한 생각을 바탕으로 Good Hash Function을 어떻게 판단해볼 수 있을 지에 대해서 알아보겠습니다.

Contents

• Chi Squared test
• Avalanche Effect
• FillFactor