hash是什么？
– 来自百科的解释
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
我经常能见到的hash算法有 MD5，CRC32, SHA
此外，还有RSHash，JSHash，PJWHash，ELFHash，BKDRHash，SDBMHash，DJBHash，APHash 等等一些知名的字符串hash算法
早先接触hash的时候， 我常常在想自己也可以很容易构造出来一个hash函数， 我只用把原字符串的单个字母转换成数字逐一或加或减，或乘或除，辅以混淆，移位，拆解分组等；得到的值按固定长度取模不就行了？
实际上，确实是可以的，只要符合hash的定义就行了，直到看到了一句话
一切没有数学理论证明的hash算法，都是玄学hash
玄学hash，是不是感到很侮辱？
什么样的hash不是玄学hash？数学理论到底要证明的是什么？为什么上述知名的hash算法被大众认可，他们哪方面的表现比较优异？
hash函数三大特性
- 一致性 —— 等价（equal）的key必然产生相等的hash code
- 高效性 —— 高效的计算
- 均匀性 —— 均匀地散列所有的key
满足以上三个特性的hash就是好的hash函数
-
一致性
这个比较好理解，输入一个值A，只能得到一个hash值B，任何时候输入值A，得到的hash值永远是B；这个是很容易理解，很容易实现，也很容易证明的
-
高效性
尽可能的降低计算复杂度，和节省内存开销
-
均匀性
均匀性是hash算法的精髓所在，以下单独讲
均匀性
hash本质是把把原空间的一个数据集映射到另外一个空间，理论上的完美无碰撞需要映射到的空间不小于原空间，但是实际上hash函数的目的就是把原空间的数据映射到一个更小的空间，以方便处理。
均匀性的要求带来两个效果
- 减少空间浪费
- 减少hash冲突（碰撞）
举个例子：
现在有10个球，编号是1-10；现在需要把放进一个组编号为1-10的盒子里
原始数据空间是10，映射的数据空间也是10；只需要进行 把球的编号按10取模+1 即为盒子编号 就能实现完美无碰撞的映射，不过如果球变成20个， 30个…. （编号自增长）； 我们的碰撞概率就会直线上升
但是如果hash 算法是 把球的编号按7取模+1， 那么第2，3，4号盒子就会装2个球， 第8，9，10 号盒子永远是空的，这个就造成了冲突和浪费
再比如：
依然还是10个盒子，盒子的编号依然是1-10； 不过球的编号由于某种原因变成了，2，4，6，8 …. 全是偶数
那么原来 把球的编号按10取模+1 的这种hash方式显然也不行了;
通过上述例子我们就能清楚的知道如何设计出一个好的hash函数：
- 增大 映射空间/原空间 的大小
这个很明显，映射空间/原空间 的比值大，碰撞的概率就可能小了。 当这个比值大于等于1时，就可以实现无碰撞。 - 把原数据集映射到较小空间时尽可能的均匀
本质上为了减少hash冲突，其实hash冲突减少了，就意味着空间得到了有效利用，也就更加均匀了 - 结合原空间数据的数据特征
我们在处理原空间的数据集时，数据集一般都会有特征，而且不会是原空间的全集。换句话说，我们要处理的数据一般只会是原空间所有数据的一部分，而且数据集有一定特征（数据元素出现的概率的不同）。比如四个字组成的成语，全集是所有汉字都参与的4位的排列组合，而实际成语是极其有限的
一个好的hash函数要具备良好的随机性，它的模型等同于：把k个球随机放入n个盒子，碰撞次数定义为有球的总数k减去有球的盒的个数； 我们讲随机性，指的是它可以把有序的值完全打乱，就混乱程度来说，看起来和随机无异；有些时候会讲hash值具备不可预测性，即你无法根据原始值预测它的hash值会落到那个区间
由于我们不能完全预知原空间数据的数据特征，所以一般哈希函数用质数参与运算这就是为了使得有特征的数据集也能均匀映射到映射空间
BKDRHash
BYVoid对常用的几种字符串哈希函数进行了一次小小的评测。其评测结果，按照得分从高到低依次为BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash。
BKDRHash 容易理解容易实现，公式就是递归求解 hash = (hash * s) + uint64(str[i]) 最后返回 hash % m
为什么s一般取值为131，因为前面的字符串数组a[n]中，取得的字符的为ascii码，数值<=127，为了尽可能保证获取的hash值的唯一性，因此需要让s为一个大于127的质数，而为了提高散列密度，又要使s尽可能小，因此，大于127的最小质数，就是131。这个值具有最佳的散列质量和散列密度。
来自大神的解释
package main
import "fmt"
func main() {
hashValue := BKDRHash("Are you ok? thank you very much!")
fmt.Print(hashValue)
}
func BKDRHash(str string) uint64 {
seed := uint64(131) // 31 131 1313 13131 131313 etc..
hash := uint64(0)
for i := 0; i < len(str); i++ {
hash = (hash * seed) + uint64(str[i])
}
// long int 的上限值，这里可以替换为得到的数据与散列表的大小NHASH进行mod运算 hash % HLEN
// 0x7fffffff = 2147483647 = (1 << 31) - 1
return hash & 0x7FFFFFFF
}
结语
“一切没有数学理论证明的hash算法，都是玄学hash”