认识达内从这里开始

认真做教育专心促就业

如何高效的处理亿万级数据？（3）

发布：青岛达内
来源：青岛达内
时间：2019-03-20 13:59

青岛达内的小编总结，平方散列法
求index是非常频繁的操作，而乘法的运算要比除法来得省时，所以我们考虑把除法换成乘法和一个位移操作。公式：
index = （value * value）》 28
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0--非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index.
斐波那契（Fibonacci）散列法
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
1,对于16位整数而言，这个乘数是40503
2,对于32位整数而言，这个乘数是2654435769
3,对于64位整数而言，这个乘数是11400714819323198485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是着名的斐波那契数列，如果你还有兴趣，就到网上查找一下“斐波那契数列”等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合，很神奇，对么？

青岛达内

对我们常见的32位整数而言，公式：
index = （value * 2654435769）》 28
如果用这种斐波那契散列法的话，那我上面的图就变成这样了：
很明显，用斐波那契散列法调整之后要比原来的取模散列法好很多。适用范围
快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。
基本原理及要点
Hash函数选择，针对字符串，整数，排列，具体相应的hash方法
碰撞处理，一种是开放哈希法，亦拉链法；另一种就是closed hashing,也称开地址法，opened addressing.
扩展
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing.2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2,给T1和T2分别配备一个哈希函数，h1和h2.在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key].这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key,就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash,同时查找两个位置。
以上就是青岛达内给大家做的内容详解，更多关于UI的学习，请继续关注青岛达内

< 上一篇：如何高效的处理亿万级数据？（2）

下一篇：如何高效的处理亿万级数据？（4） >