哈希函数的设计

记得上次看到有哈希表的设计，我觉得那个比较困难。 这里分享一个别人的哈希函数 hash function 的设计文章，读起来大概十五分钟:

https://nullprogram.com/blog/2018/07/31/ https://github.com/skeeto/hash-prospector

Takeaway:

• 几个现成的哈希函数

• 如果哈希函数是 1:1 (reversible) 那么是没有哈希冲突的

My focus is on integer hash functions: a function that accepts an n-bit integer and returns an n-bit integer. One of the important properties of an integer hash function is that it maps its inputs to outputs 1:1. In other words, there are no collisions

• 两个设计和评价哈希函数的角度: 公平和偏离

There are two key properties I’m looking for in randomly generated hash functions. 1. High avalanche effect. When I flip one input bit, the output bits should each flip with a 50% chance. 2. Low bias. Ideally there is no correlation between which output bits flip for a particular flipped input bit.

(我个人觉得这两点都是在说 bias)