HashMap扩容与树化
HashMap源码
package com.lyc._Map;
import java.util.HashMap;
public class HashMapSource1 {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("java",10);//ok
hashMap.put("python",20);//ok
hashMap.put("java",30);//替换
System.out.println("map="+hashMap);
//解读HashMap源码
/*
* 1.执行构造器，new HashMap() =>初始化加载因子 loadfactor=0.75 ，HashMap$Node table=[null];
* 2.执行 put方法
* //K = java V= 10
* public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//执行put，调用hash方法，计算key的hash值，
//static final int hash(Object key) {
// int h;
// return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//右移十六位
// }
*3.执行最核心的putval方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//辅助变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果底层的table数组为空，或者tabl.length=0 就扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//1.取出hash值对应的table表的索引位置的node，如果node为null，
//则直接把加入的k-v 创建成（new成）一个node，加入到该位置
//2.如果其索引的位置不等于空就执行else
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断3种情况，
1.索引位置key的hash值是否相同，并且满足
2.((k = p.key) == key ，是否k是同一个对象，或者(key != null && key.equals(k)) 不是同一个对象，但那是内容相同，
（判断内容是都相同用equals方法）
//符合第一个条件，并满足第二个条件中的一个时，就认为发现了相同的对象，就不能加入新的k-v了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//e是辅助变量， p是：(p = tab[i = (n - 1) & hash]) 即：原hash坑主，在if判断的时候， 就已经将原索引的Node节点获取了
e = p;
//判断这个对象是否是一个树，如果是一个红黑树，则按照红黑树的方式处理
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果找到的是链表，所以将新加入的值，与该hash位置对应的链表中的每个元素进行比较，没有重复，则添加到末尾
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//如果比较一圈都没发现与它相同的，则将其加入到链表的最后
p.next = newNode(hash, key, value, null);
//加入后判断链表元素的个数是否已经到8个，到8个后
//就调用treefyBin方法进行树化，但是树化还有一个条件，tabl.length>=64
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果比较过程发现有相同，则退出循环，在后面进行替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果key 相同，value不同，进行的替换
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;//替换操作
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//每增加一个node，modcount就会++，如果发现
if (++size > threshold) //注意这里threshold=12是临界值，不是到了16才扩容的
resize();
afterNodeInsertion(evict);
return null;
}
* */
}
}
查看HashMap树化
- 当table中的一个结点的链表个数大于8个，时触发扩容table
-
满足链表大于8，table大于64时，触发的树化
演示用的代码
package com.lyc._Map;
import java.util.HashMap;
import java.util.Objects;
public class HashMapSource2 {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
for (int i=0;i<=12;i++){
hashMap.put(new A(i),"hello");//十二个 k-v
}
System.out.println(hashMap);
}
}
class A{
private int num;
public A(int num){
this.num = num;
}
//重写 hashCode方法，使A对象返回的hash值一样
@Override
public int hashCode() {
return 100;
}
@Override
public String toString() {
return "\nA{" +
"num=" + num +
'}';
}
}
table列表触发扩容
-
当table列表中的元素到达12，时就会触发table的扩容
-
每次扩容翻倍
-
加载因子为容量的0.75，初始为12
- 演示代码
package com.lyc._Map;
import java.util.HashMap;
public class HashMapSource03 {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
for (int i = 0; i <100; i++) {
hashMap.put(new A2(i),"hello");
}
System.out.println(hashMap);
}
}
class A2{
private int num;
public A2(int num) {
this.num = num;
}
@Override
public String toString() {
return "\nA2{" +
"num=" + num +
'}';
}
}