东莞网站制作哪里好,如何给wordpress导航添加图标,asp.net 微网站开发教程,如何做英文网站如何计算#xff0c;一对key/value应该放在哪个哈希桶大家都知道#xff0c;hashmap底层是数组链表(不讨论红黑树的情况)#xff0c;其中#xff0c;这个数组#xff0c;我们一般叫做哈希桶#xff0c;大家如果去看jdk的源码#xff0c;会发现里面有一些变量#xff0c…如何计算一对key/value应该放在哪个哈希桶大家都知道hashmap底层是数组链表(不讨论红黑树的情况)其中这个数组我们一般叫做哈希桶大家如果去看jdk的源码会发现里面有一些变量叫做bin这个bin就是桶的意思结合语境就是哈希桶。这里举个例子假设一个hashmap的数组长度为4(0000 0100)那么该hashmap就有4个哈希桶分别为bucket[0]、bucket[1]、bucket[2]、bucket[3]。现在有两个nodehashcode分别是1(0000 0001)5(0000 0101). 我们当然知道这两个node都应该放入第一个桶毕竟1 mod 45 mod 4的结果都是1。但是在代码里可不是用取模的方法来计算的而是使用下面的方式int entryNodeIndex (tableLength - 1) hash;应该说在tableLength的值为2的n次幂的时候两者是等价的但是因为位运算的效率更高因此代码一般都使用位运算替代取模运算。下面我们看看具体怎么计算此处tableLength即为哈希表的长度此处为4. 4 - 1为33的二进制表示为0000 0011那么和我们的1(0000 0001)相与0000 0001 -------- 10000 0011 -------- 3(tableLength - 1)相与(同为1则为1否则为0)0000 0001 -------- 1结果为1所以应该放在第1个哈希桶即数组下标为1的node。接下来看看5这个hashcode的节点要放在什么位置是怎么计算0000 0101 -------- 50000 0011 -------- 3(tableLength - 1)相与(同为1则为1否则为0)后结果0000 0001 -------- 1扩容时是怎么对一个hash桶进行transfer的此处具体的整个transfer的细节我们本讲不会涉及太多不过大体的逻辑我们可以来想一想。以前面为例哈希表一共4个桶其中bucket[1]里面存放了两个元素假设是a、b其hashcode分别是15.现在假设我们要扩容一般来说扩容的时候都是新建一个bucket数组其容量为旧表的一倍这里旧表为4那新表就是8.那新表建立起来了旧表里的元素就得搬到新表里面去等所有元素都搬到新表了就会把新表和旧表的指针交换。如下java.util.concurrent.ConcurrentHashMap#transferprivate transient volatile Node[] nextTable;transient volatile Node[] table;if (finishing) {// 1nextTable null;// 2table nextTab;// 3sizeCtl (tabLength 1) - (tabLength 1);return;}1处将fieldnextTable(也就是新表)设为null扩容完了这个field就会设为null2处将局部变量nextTab赋值给table这个局部变量nextTab里就是当前已经扩容完毕的新表3处修改表的sizeCtl为假设此处tabLength为4tabLength 1 左移1位就是8tabLength 1右移一位就是2。8 - 2 6正好就等于 8(新表容量) * 0.75。所以这里的sizeCtl就是新表容量 * 负载因子超过这个容量基本就会触发扩容。ok接着说我们要怎么从旧表往新表搬呢 那以前面的bucket[1]举例遍历这个链表计算各个node应该放到新表的什么位置不就完了吗是的理论上这么写就完事了。但是我们会怎么写呢用hashcode对新bucket数组的长度取余吗jdk对效率的追求那么高肯定不会这么写的我们看看它怎么写的java.util.concurrent.ConcurrentHashMap#transfer// 1for (Node p entryNode; p ! null; p p.next) {// 2int ph p.hash;K pk p.key;V pv p.val;// 3if ((ph tabLength) 0){lowEntryNode new Node(ph, pk, pv, lowEntryNode);}else{highEntryNode new Node(ph, pk, pv, highEntryNode);}}1处即遍历旧的哈希表的某个哈希桶假设就是遍历前面的bucket[1]里面有a/b两个元素hashcode分别为15那个。2处获取该节点的hashcode此处分别为153处如果hashcode 和 旧表长度相与结果为0则将该节点使用头插法插入新表的低位如果结果不为0则放入高位。ok什么是高位什么是低位。扩容后新的bucket数组长度为8那么前面bucket[1]中的两个元素将分别放入bucket[1]和bucket[5].ok这里的bucket[1]就是低位bucket[5]为高位。首先大家要知道hashmap中容量总是2的n次方请牢牢记住这句话。为什么要这么做你想想这样是不是扩容很方便以前hashcode 为15的都在bucket[1]而现在扩容为8后hashcode为1的还是在newbucket[1]hashcode为5的则在newbucket[5]这样的话是不是有一半的元素根本不用动这就是我觉得的最大的好处另外呢运算也比较方便都可以使用位运算代替效率更高。好的那我们现在问题来了下面这句的原理是什么if ((ph tabLength) 0){lowEntryNode new Node(ph, pk, pv, lowEntryNode);} else{highEntryNode new Node(ph, pk, pv, highEntryNode);}为啥hashcode 旧哈希表的容量 结果为0的扩容后就会在低位也就是维持位置不变呢而结果不为0的扩容后位置在高位呢背后的位运算原理(大白话)代码里用的如下判断满足这个条件去低位否则去高位。if ((ph tabLength) 0)还是用前面的例子假设当前元素为ahashcode为1和哈希桶大小4去进行与运算。0000 0001 ---- 10000 0100 ---- 旧哈希表容量4运算(同为1则为1否则为0)结果0000 0000 ---- 结果为0ok这里算出来结果为0什么情况下结果会为0呢那我们现在开始倒推什么样的数和 0000 0100 相与结果会为0???? ???? ----0000 0100 ---- 旧哈希表容量运算(同为1则为1否则为0)结果0000 0000 ---- 结果为0因为与运算的规则是同为1则为1否则都为0。那么我们这个例子里旧哈希表容量为 0000 0100假设表示为2的n次方此处n为2我们仅有第三位(第n1)为1那如果对方这一位为0那结果中的这一位就会为0那么整个数就为0.所以我们的结论是假设哈希表容量为2的n次方表示为二进制后第n1位为1那么只要我们节点的hashcode在第n1位上为0则最终结果是0.反之如果我们节点的hashcode在第n1位为1则最终结果不会是0.比如hashcode为5的时候会是什么样子0000 0101 ---- 50000 0100 ---- 旧哈希表容量运算(同为1则为1否则为0)结果0000 0100 ---- 结果为4此时5这个hashcode在第n1位上为1所以结果不为0。至此我们离答案好像还很远。ok不慌继续。假设现在扩容了新bucket数组长度为8.a元素hashcode依然是1a元素应该放到新bucket数组的哪个bucket里呢我们用前面说的这个算法来计算int entryNodeIndex (tableLength - 1) hash;0000 0001 ---- 10000 0111 ---- 8 - 1 7运算(同为1则为1否则为0)结果0000 0001 ---- 结果为1结果没错确实应该放到新bucket[1]但怎么推论出来呢// 1if ((ph tabLength) 0){// 2lowEntryNode new Node(ph, pk, pv, lowEntryNode);}也就是说假设一个数满足1处的条件(ph tabLength) 0那怎么推论出2呢即应该在低位呢ok条件1前面分析了可以得出这个数第n1位为0.接下来看看数组长度 - 1这个数。数组长度2的n次方二进制表示1出现的位置数组长度-1数组长度-1的二进制22的1次方0000 0010第2位10000 000142的2次方0000 0100第3位30000 001182的3次方0000 1000第4位70000 0111好了两个数都有了???????0??????? -- 1 节点的hashcode第n 1位为0000000010000000 -- 2 老数组000000100000000 -- 3 新数组的长度等于老数组长度 * 2000000011111111 -- 4 新数组的长度 - 1运算1和4相与大家注意看红字部分还有框出来的那一列这一列为0导致最终结果肯定是比2那一行的数字小2这行不就是老数组的长度吗那你比老数组小你比这一行小在新数组里就只能在低位了。反之如果节点的hashcode这一位为1那么最终结果至少是大于等于2这一行的数字所以会放在高位。参考资料原文https://www.cnblogs.com/grey-wolf/p/13057567.html
