How to make a Hash Function?

일반적인 Data들에 대해서 좋은 성능을 지닌 매우 다양한 Hash Function들이 존재합니다.

Hash Table을 만들기 위해서 시중에 나와있는 이러한 Hash Function들을 사용하는 것은 좋은 선택이 될 수 있습니다.

하지만 만약 사용할 key들을 미리 알고 있고, 이에 대한 특징을 제대로 파악하고 있다면

일반적으로 널리 쓰이는 Hash Function들보다 좀 더 최적화된 Hash Function을 만들어 보는 것을 시도할 수 있습니다.

그렇다면 Hash Function을 만들기 위한 primitive들은 어떤 것들이 있을까요?

이에 대한 내용을 The Art of Computer Programming, vol. 3 by Donald Knuth에서 소개된 Hash Function들을 통해 알아봅니다.

Contents

• Division Hashing
• Middle Square Hashing
• Multiplicative Hashing
• Fibonacci Hashing
• Algebraic Hashing