要讲一致性Hash原理,先从一般性Hash讲起,其实Hash的本质就是一个长度可变的数组,那为什么Hash的时间复杂度是O(1),而其他类型的数据结构查找都是要遍历来,遍历去,即便是树,二叉树,也是要经过几次比对...数组长度变化就要进行一次rehash,也就是重新计算每个对象在数组中的位置,即hash值.我们可以来看一下这段代码,虽然他没有HashMap那么复杂,但原理是一样,只不过计算Hash值的时候只用了最简单的取模...知道了普通Hash的原理,我们来看看一致性Hash.一致性Hash是由一个固定长度的Hash环构成,大小为2的32次方.一般用在服务器集群的增删节点的处理上,根据节点名称的Hash值(其分布为[0, 232...我们知道查找最快的是树,比数组,链表都快.所以我们就选用红黑树来建立这个Hash环,而Java中已经有TreeMap和TreeSet都实现了红黑树.以TreeMap为例,TreeMap本身提供了一个tailMap...) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;