成都网站建设制作价格,婚恋网站做期货现货贵金属的人,品牌建设策划方案,徐州住房与城乡建设部网站1、本人博客《HashMap、HashSet底层原理分析》 2、本人博客《若debug时显示的Hashmap没有table、size等元素时#xff0c;查看第19条》
结论
1、链表长度大于8时(插入第9条时)#xff0c;会触发树化(treeifyBin)方法#xff0c;但是不一定会树化#xff0c;若数组大小小于…1、本人博客《HashMap、HashSet底层原理分析》 2、本人博客《若debug时显示的Hashmap没有table、size等元素时查看第19条》
结论
1、链表长度大于8时(插入第9条时)会触发树化(treeifyBin)方法但是不一定会树化若数组大小小于64时则会先扩容。 2、假设扩容后该链表重新计算Hash后还是放在同一个数组下标时则会出现链表长度大于8时未树化的情况。
jdk8源码(treeifyBin)
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;// MIN_TREEIFY_CAPACITY 64// 链表长度小于64时会优先扩容if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();else if ((e tab[index (n - 1) hash]) ! null) {TreeNodeK,V hd null, tl null;do {TreeNodeK,V p replacementTreeNode(e, null);if (tl null)hd p;else {p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);if ((tab[index] hd) ! null)hd.treeify(tab);}
}测试源码(大于8时未树化)
import java.util.HashMap;
import java.util.Objects;public class HashmapTest {public static void main(String[] args) {HashMapUser,User hashMap new HashMap();// 同一链表插入8条for (int i 0; i 8; i) {hashMap.put(new User(张三, 18),new User(张三, i));}// 插入第九条链表长度大于8会进入treeifyBin树化方法但是未树化会执行扩容方法// 默认数组大小16扩容到32// 链表长度变成了9个Node节点并非红黑树hashMap.put(new User(张三, 18),new User(张三, 9));// 插入第10条链表长度大于8会进入treeifyBin树化方法但是未树化会执行扩容方法// 数组大小由32扩容到了64// 链表长度变成了10个Node节点并非红黑树hashMap.put(new User(张三, 18),new User(张三, 10));// 插入第十一条时树化// 数组容量还是64未触发扩容// 链表变成红黑树节点由Node变成TreeNodehashMap.put(new User(张三, 18),new User(张三, 11));}
}// 重写hashCode方法保证值一样是hashcode是一样的可以使值一样的对象出现在同一链表上
class User{private String name;private int age;public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}public User(String name, int age) {this.name name;this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic int hashCode() {return Objects.hash(name, age);}
}插入第九条时的Hashmap 插入第十条时结果是一样的只是数组扩容到了64 1、数组长度扩容到了32 2、Hashmap中保存了9个数据均在同一条链表 3、节点为Node节点并不是treenode(红黑树) 插入第十一条时的Hashmap 1、数组大小为64 2、节点变成了treenode(红黑树)
测试源码(大于8时树化)
初始化Hashmap时直接大于等于64则同一个链表插入第九条时直接执行了树化。 treeifyBin方法中只有数组长度小于64时才会执行扩容方法否则则是树化
// 初始化大小其他同上插入第九条时节点就变成了treenode
HashMapUser,User hashMap new HashMap(64);插入第九条时的Hashmap 1、数组大小为64 2、节点变成了treenode(红黑树)
