外贸模板网站,网页链接下载,成立公司需要哪些资料,用服务器ip做网站域名HashMap的扩容原理 1.扩容流程图 注#xff1a;拆分链表的规则
这里拆分链表时的一个比较#xff1a;e.hash oldCap 0 意思是#xff1a;某一个节点的hash值和老数组容量求运算。如果等于0#xff0c;当前元素在老数组中的位置就是在新数组中的位置。如果不等… HashMap的扩容原理 1.扩容流程图 注拆分链表的规则
这里拆分链表时的一个比较e.hash oldCap 0 意思是某一个节点的hash值和老数组容量求运算。如果等于0当前元素在老数组中的位置就是在新数组中的位置。如果不等于0它存储的位置是原来老数组中的位置 老数组容量。
例假设老数组容量是16新数组就是32
现在要拆分标明的这个节点该点在老数组中的位置是3。如果该点的hash oldCap 0。则把该点挂在新数组的也是3的位置。如果不为0则挂在 3 16 19 的位置。 2.扩容源码分析(有注释) jdk8
//扩容、初始化数组
final NodeK,V[] resize() {NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap老数组容量设置为0int oldCap (oldTab null) ? 0 : oldTab.length;//老的扩容阈值int oldThr threshold;int newCap, newThr 0;//判断数组容量是否大于0大于0说明数组已经初始化if (oldCap 0) {//判断当前数组长度是否大于最大数组长度if (oldCap MAXIMUM_CAPACITY) {//如果是将扩容阈值直接设置为int类型的最大数值并直接返回threshold Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap*2//所以每次扩容就是原来的两倍//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold 等价于oldThr*2}//如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;//数组未初始化的情况将阈值和扩容因子都设置为默认值else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;// 默认容量16// 默认加载因子 * 默认容量 16 * 0.75 12// 阈值超过就触发扩容逻辑newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候扩容阈值是没有赋值的if (newThr 0) {//创建阈值float ft (float)newCap * loadFactor;//判断新容量和新阈值是否大于最大容量newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//计算出来的阈值赋值threshold newThr;SuppressWarnings({rawtypes,unchecked})//根据上边计算得出的容量 创建新的数组 NodeK,V[] newTab (NodeK,V[])new Node[newCap];//赋值table newTab;// table就是我们存储数据的数组//扩容操作判断不为空证明不是初始化数组if (oldTab ! null) {//遍历数组for (int j 0; j oldCap; j) {NodeK,V e;//判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作if ((e oldTab[j]) ! null) {//将数组位置置空oldTab[j] null;//判断是否有下个节点if (e.next null)//如果没有就重新计算在新数组中的下标并放进去newTab[e.hash (newCap - 1)] e;//有下个节点的情况并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且没有树化链表形式else {//比如老数组容量是16那下标就为0-15//扩容操作*2容量就变为32下标为0-31//低位0-15高位16-31//定义了四个变量// 低位头 低位尾NodeK,V loHead null, loTail null;// 高位头 高位尾NodeK,V hiHead null, hiTail null;//下个节点NodeK,V next;//循环遍历do {//取出next节点next e.next;//通过 与操作 计算得出结果为0if ((e.hash oldCap) 0) {//如果低位尾为null证明当前数组位置为空没有任何数据if (loTail null)//将e值放入低位头loHead e;//低位尾不为null证明已经有数据了else//将数据放入next节点loTail.next e;//记录低位尾数据loTail e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null证明当前数组位置为空没有任何数据if (hiTail null)//将e值放入高位头hiHead e;//高位尾不为null证明已经有数据了else//将数据放入next节点hiTail.next e;//记录高位尾数据hiTail e;}} //如果e不为空证明没有到链表尾部继续执行循环while ((e next) ! null);//低位尾如果记录的有数据是链表if (loTail ! null) {//将下一个元素置空loTail.next null;//将低位头放入新数组的原下标位置newTab[j] loHead;}//高位尾如果记录的有数据是链表if (hiTail ! null) {//将下一个元素置空hiTail.next null;//将高位头放入新数组的(原下标原数组容量)位置newTab[j oldCap] hiHead;}}}}}//返回新的数组对象return newTab;}
小结
