哈希函数的设计

[allAboutDbmss]

记得上次看到有哈希表的设计，我觉得那个比较困难。 这里分享一个别人的哈希函数 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)

[documentzhangx66]

上次那老哥说的是 Minimal_perfect_hash_function ，与 我们常见的 MD5 、SHA1 这类哈希，根本是不同的东西，只是名称中都包含了 HASH ，于是大家先入为主地，以为那位老哥在说 MD5 、SHA1 之类的主流哈希算法。那位老哥说的那种更像是根据 value 反推 ID key 的 index 查找算法。

[allAboutDbmss]

@documentzhangx66 是的
我这个链接就是一个哈希表哈希函数 需要公平和高性能
所以这个也不是 md5 甚至一些加密哈希算法