Все рассматриваемые ниже хэш-функции используют подход static hashing — они пытаются предоставить такую хэш-функцию, которая будет работать отлично с любыми данными.
The best way to have a good average-case performance for any data is to use a suitable family of hash functions and choose a hash function at random from this family at runtime, independent of the data to be hashed. Этот подход называется random hashing. Он включает в себя universal hashing, который также отлично работает.
Achievable properties of random hashing
One approach to hash vectors is to use a cryptographic hash function such as SHA-256. Such functions are complex and sufficiently random for hash table applications. On machines with specialized instructions, cryptographic functions can be quite efficient.
Строки хэшируем так:
Introduction to Algorithms (Fourth Edition) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022)