这篇文章主要介绍“Java一致性哈希算法举例分析”，在日常操作中，相信很多人在Java一致性哈希算法举例分析问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java一致性哈希算法举例分析”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！google 有一个 Jump consistent hash 算法，可以通过数学运算做到和一致性哈希效果一样好的平衡性。
先看代码，下面就是全部的代码。是不是感觉不可思议，这个代码的语法全部都懂，但是合在一起我们就看不懂了。
我第一眼看到这个代码的时候，也是一脸懵逼的。这个算法是 Google 的 John Lamping 和 Eric Veach 创造的。
一致性哈希算法有两个目标：平衡性。即把数据平均的分布在所有节点中。单调性。即节点的数量变化时，只需要把一部分数据从旧节点移动到新节点，不需要做其他的移动。我们根据这个单调性可以推算出一些性质来。
这里先令f(key, n)为一致性哈希算法，输出的为[0,n)之间的数字，代表数据在对应的节点上。n=1时，对于任意的key，输出应该都是0。n=2时，为了保持均匀，应该有1/2的结果保持为0，1/2的结果输出为1。n=3时，应该有1/3的结果保持为0，1/3的结果保持为1，1/3的结果保持为2。依次递推，节点数由n变为n+1时，f(key, n)里面应该有n/(n+1)的结果不变，有1/(n+1)的结果变为n。这个使用概率公式来表示，就是这样的代码。关于这个算法直接看可能还是看不懂。
所以需要使用实际数据模拟一下，见下图。关键在于n=2到n=3的过程，每个数字的概率从1/2转化到了1/3。之后，我们可以得出一个规律：增加一个节点，数据不发生变化的概率是n/(n+1)再乘以之前每个数字的概率1/n，就可以得出每个数字最新的概率1/(n+1)由此，可以轻松计算出n=4各数字的概率为1/4。自此，我们可以确定这个算法确实是有效的。这个算法唯一的缺点是复杂度太高，是O( 香港云主机n)的。
所以需要进行优化。在上一小节中，我们了解到f(key, n)算法的正确性。
除了复杂度是O(n)外，我们还可以确定，循环越往后，结果改变的概率会越来越低。结果改变指的是，增加一个节点后，一个固定的key输出的结果发生了改变。
如果我们能够快速计算出这个固定的key在哪些节点下发生了改变，就可以快速计算出最终答案。假设某一次结果是b，经过若干次概率测试，下一次改变为a，则从b到a-1这中间，不管节点如何变化，这个key的结果都是不会变化的。
根据上一小节的到的概率变化公式，新增一个节点数字不变化的概率是n/(n+1)。
那从b到i不变化的概率就是b/i（中间的抵消了）。如果我们有一个均匀的随机函数r，当r时，由于f(i)=f(b)。
那么i的上界就是(b+1)/r。
这个上限也是下一次key发生变化的节点数量，由此可以得出下面的代码。r是均匀的，所以期望是1/2。
这样，代码中j就是按照指数级增长的，平均复杂度就是O(log(n))了。回头看看第一个代码，就可以看懂代码了。第一个key=key*x+1算是一个伪随机生成器。
而j=(b+1)*x/y则是上面的求上界的公式，其中y/x通过浮点数运算来产生(0,1)内的一个随机数。
自此，这个代码就可以看懂了。到此，关于“Java一致性哈希算法举例分析”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注开发云网站，小编会继续努力为大家带来更多实用的文章！
这期内容当中小编将会给大家带来有关C#中sealed关键字有什么用，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。1. seal 香港云主机ed关键字 当对一个类应用 sealed 修饰符时，此修饰符会阻止其他类从该类继承。类…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
