青岛哪个网站建设公司价格低还能好一些网站流量排行

1、本人博客《HashMap、HashSet底层原理分析》
2、本人博客《若debug时显示的Hashmap没有table、size等元素时，查看第19条》

结论

1、链表长度大于8时(插入第9条时)，会触发树化(treeifyBin)方法，但是不一定会树化，若数组大小小于64时，则会先扩容。
2、假设扩容后该链表重新计算Hash后还是放在同一个数组下标时，则会出现链表长度大于8时，未树化的情况。

jdk8源码(treeifyBin)

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,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) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,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) {HashMap<User,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
HashMap<User,User> hashMap = new HashMap<>(64);

插入第九条时的Hashmap
1、数组大小为64
2、节点变成了treenode(红黑树)