-
day24--Java集合07
14.HashMap
14.1HashMap介绍
-
Map接口的常用实现类：HashMap、Hashtable、Properties
-
HashMap是Map接口使用频率最高的实现类
-
HashMap是以key-value对的方式来存储数据（HashMap$Node类型）
-
key不能重复，value可以重复。允许使用null键和null值
-
如果添加相同的key键，则会覆盖原来的key-value，等同于修改（key不会替换，value会替换）
-
与HashSet一样，不保证映射的顺序，因为底层是以hash表的顺序来存储的。（JDK8的HashMap底层：数组+链表+红黑树）
-
HashMap没有实现同步，因此线程不安全，方法没有做同步互斥的操作，没有synchronized
14.2HashMap底层扩容机制
- （k,v）是一个Node，实现了Map.Entry<K,V>，查看HashMap的源码可以看到
- jdk7.0 的HashMap底层实现[数组+链表]，jdk8.0底层[数组+链表+红黑树]
详见10.2HashSet的底层扩容机制
- HashMap底层维护了Node类型的数组table，默认为null
- 当创建对象时，将加载因子（loadfactor）初始化为0.75
- 当添加key-value时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素则直接添加；如果该索引处有元素，继续判断该元素的key是否和准备加入的key相等。若相等，则直接替换value；若不相等，需要判断是树结构还是链表结构，作出相应处理。如果添加是发现容量还不够，则需要扩容。
- 第一次添加，则需要扩容table容量为16，临界值（threshold）为（0.75*16=）12
- 以后再扩容，则需要扩容为table的容量为之前的两倍，临界值也为原来的两倍，即24.以此类推
- 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认为8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）。
例子：
|
|
package li.map.hashmap; |
|
|
|
|
|
import java.util.HashMap; |
|
|
|
|
|
|
|
|
public class HashMapSource { |
|
|
public static void main(String[] args) { |
|
|
HashMap map = new HashMap(); |
|
|
map.put("java",10);//ok |
|
|
map.put("php",10);//ok |
|
|
map.put("java",20);//替换value |
|
|
|
|
|
System.out.println(map);//{java=20, php=10} |
|
|
} |
|
|
} |
执行过程如下：
-
执行构造器
newHashMap();初始化加载因子 loadfactor = 0.75
HashMap$Node[ ] = null
-
执行put（），调用hash（）方法计算key的值
可以看到，如果传入的参数key为空的话，就返回0；如果不为空，则求出 key 的 hashCode 值，然后将hashCode 值右移16位并且与原来的 hashCode 值进行 ^(按位异或) 操作，并返回这个哈希值
|
|
public V put(K key, V value) {//K="java" value= 10 |
|
|
return putVal(hash(key), key, value, false, true); |
|
|
} |
|
|
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;//定义了辅助变量 |
|
|
//这里定义的tablejiushi HashMap的一个数组，类型是Node[]数组 |
|
|
if ((tab = table) == null || (n = tab.length) == 0)//if 语句表示，如果当前table是null，或者大小=0，则进行第一次扩容，扩容到16个空间 |
|
|
n = (tab = resize()).length;//如果为第一次扩容，此时初始的table已经变成容量为16的数组 |
|
|
|
|
|
/* |
|
|
1.根据key，得到hash 去计算key应该放到table表的哪个索引位置，并且把这个未知的对象赋给赋值变量p 2.再判断p是否为空 |
|
|
2.1如果p为空，表示该位置还没存放元素，就创建一个Node (key="java", value=PRESENT)并把数 据放在该位置--table[i]=newNode(hash, key, value, null); |
|
|
*/ |
|
|
if ((p = tab[i = (n - 1) & hash]) == null) |
|
|
tab[i] = newNode(hash, key, value, null); |
|
|
|
|
|
|
|
|
else { |
|
|
//2.2如果不为空，就会进入else语句 |
|
|
Node<K,V> e; K k;//定义辅助变量 |
|
|
/*这里的p指向当前索引所在的对象（由上面的p = tab[i = (n - 1) & hash])计算出索引位置），如 果当前索引位置对应链表的第一个元素的哈希值 和 准备添加的key的哈希值 一样， |
|
|
并且 满足下面两个条件之一： |
|
|
1.准备加入的key 和 p指向的Node节点 的key 是同一个对象：(k = p.key) == key |
|
|
2.p指向的Node节点的key 的equals()和准备加入的key比较后相同 并且key不等于null：(key != null && key.equals(k)) |
|
|
就不加入 只是换原来的元素（不插入新结点只是替换值） |
|
|
*/ |
|
|
if (p.hash == hash && |
|
|
((k = p.key) == key || (key != null && key.equals(k)))) |
|
|
e = p; |
|
|
|
|
|
//再判断p是否是一颗红黑树 |
|
|
//如果是红黑树，就调用putTreeVal（）方法来进行添加 |
|
|
else if (p instanceof TreeNode) |
|
|
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); |
|
|
|
|
|
else { //如果table对应索引位置已经是一个链表了，就使用for循环依次比较 |
|
|
//（1）依次和该链表的每个元素都比较后 都不相同，就则将数据加入到该链表的最后 |
|
|
for (int binCount = 0; ; ++binCount) { |
|
|
if ((e = p.next) == null) {//先赋值再判断 |
|
|
p.next = newNode(hash, key, value, null); |
|
|
//注意：把元素添加到链表之后立即 判断该链表是否已经达到8个节点，如果已经达到则 //调用 treeifyBin()对当前链表进行树化（转成红黑树） |
|
|
//在转成红黑树时 还要进行一个判断： |
|
|
//如果该table数组的为空或者大小小于64，则对table数组进行扩容 |
|
|
//如果上面条件不成立，即数组大小大于等于64且链表数量达到8个，就转成红黑树 |
|
|
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st |
|
|
treeifyBin(tab, hash); |
|
|
break; |
|
|
} |
|
|
|
|
|
//（2）如果在依次和该链表的每个元素比较的过程中发现如果有相同情况，就直接break |
|
|
if (e.hash == hash && |
|
|
((k = e.key) == key || (key != null && key.equals(k)))) |
|
|
break; |
|
|
p = e;//在上面for循环条件已经把p.next赋值给e了，这里e又赋值给p 其实就是将p指针指 //向p.next，然后再进行新一轮的判断，如此循环，直到有满足上面if语句的条件为止 |
|
|
} |
|
|
} |
|
|
|
|
|
if (e != null) { // existing mapping for key |
|
|
V oldValue = e.value; |
|
|
if (!onlyIfAbsent || oldValue == null) |
|
|
e.value = value;//替换，key对应value |
|
|
afterNodeAccess(e); |
|
|
return oldValue; |
|
|
} |
|
|
} |
|
|
|
|
|
|
|
|
++modCount;//每增加一个Node，就size++ |
|
|
if (++size > threshold)//当使用的容量 > 临界值时，就扩容 |
|
|
resize(); |
|
|
afterNodeInsertion(evict); |
|
|
return null; |
|
|
} |
PS:关于树化
|
|
for (int binCount = 0; ; ++binCount) { |
|
|
//（1）依次和该链表的每个元素都比较后 都不相同，就则将数据加入到该链表的最后 |
|
|
if ((e = p.next) == null) {//先赋值再判断 |
|
|
p.next = newNode(hash, key, value, null); |
|
|
|
|
|
//注意：把元素添加到链表之后立即 判断该链表是否已经达到8个节点，如果已经达到则 //调用 treeifyBin()对当前链表进行树化（转成红黑树） |
|
|
//在转成红黑树时 还要进行一个判断： |
|
|
//如果该table数组的为空或者大小小于64，则对table数组进行扩容 |
|
|
//如果上面条件不成立，即数组大小大于等于64且链表数量达到8个，就转成红黑树 |
|
|
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st |
|
|
treeifyBin(tab, hash); |
|
|
break; |
|
|
} |
|
|
|
|
|
//（2）如果在依次和该链表的每个元素比较的过程中发现如果有相同情况，就直接break |
|
|
if (e.hash == hash && |
|
|
((k = e.key) == key || (key != null && key.equals(k)))) |
|
|
break; |
|
|
p = e;//在上面for循环条件已经把p.next赋值给e了，这里e又赋值给p 其实就是将p指针指 //向p.next，然后再进行新一轮的判断，如此循环，直到有满足上面if语句的条件为止 |
|
|
} |
遍历过程中p从第一个节点遍历到最后一个节点，但由于binCount是从0开始计数，所以在做树化判断时binCount
的值等于 链表长度 - 1（注意此时的链表长度没有算新插入的节点）
判断条件为 binCount >= TREEIFY_THRESHOLD - 1 ==> binCount+1(链表长度) >= TREEIFY_THRESHOLD
但此时链表新插入了一个节点
|
|
p.next = newNode(hash, key, value, null); |
所以链表树化的那一刻，它的真实长度应该时binCount+1+1 => 链表长度>TREEIFY_THRESHOLD(8)
即：
链表长度大于8时，treeifyBin()方法被调用
（在做树化判断时，链表长度 = binCount+1（从零计数）+1（新插入节点） = bincount +2）
（判断条件： (bincount >= 8-1) => (bincount>=7) => (bincount+2>=9) => (链表长度>=9) 长度是整数 大于等于9也就是大于8）
ps:剪枝--->如果有链表树化之后，树中的节点经过删除之后越来越少，当元素个数减少到一定程度，树会转变为了链表
14.3HashMap扩容树化触发
例子：
|
|
package li.map.hashmap; |
|
|
import java.util.HashMap; |
|
|
|
|
|
|
|
|
public class HashMapSource2 { |
|
|
public static void main(String[] args) { |
|
|
HashMap hashMap = new HashMap(); |
|
|
for (int i = 1; i <= 12; i++) { |
|
|
hashMap.put(new A(i), "hello"); |
|
|
} |
|
|
|
|
|
System.out.println(hashMap); |
|
|
} |
|
|
} |
|
|
|
|
|
class A { |
|
|
private int num; |
|
|
|
|
|
public A(int num) { |
|
|
this.num = num; |
|
|
} |
|
|
|
|
|
//A对象所有的hashcode都是100 |
|
|
|
|
|
public int hashCode() { |
|
|
return 100; |
|
|
} |
|
|
|
|
|
|
|
|
public String toString() { |
|
|
return "\nA{" + |
|
|
"num=" + num + |
|
|
'}'; |
|
|
} |
|
|
} |
如下图，打上断点，点击debug。
当HashMap初始化时，底层数组容量为null：
如下图：装入第一个元素前，数组长度扩容到16
如下图：因为重写了A类的hashCode值，所以在循环过程中元素会快速在某个索引下标上形成链表。
在table 数组的某个链表上，当链表的元素个数超过8个时，此时table数组会进行容量扩展16--->32
如下图：当链表的个数继续增加时，table数组继续进行两倍扩容：
如下图，此时量表上的元素个数为10，table数组的长度为64。
当链表上的个数继续增加时，满足了链表树化条件（链表长度>8，table长度>64），就会进行链表树化，数据存储类型变成了TreeNode
总结：
HashMap底层是数组+链表+红黑树
- HashMap第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor，0.75）=12；如果table数组容量使用到了临界值12，就会扩容到16 * 2=32，新的临界值就是32 * 0 .75=24，依此类推（两倍扩容）
注意：这里的容量计算的不仅仅是table数组上的容量，链表上的容量也算。即只要增加了一个元素，使用的容量就+1
例如：当一个table表的数组某个索引位置上存储了一个值，而这个值后面的链表存储了7个值，加起来就是8，那么在数组长度没有超过64时，再加入一个值，数组就会进行两倍扩容
-
添加一个元素时，先得到一个hash值--会转成--索引值
-
找到存储数据表table，看这个索引位置是否已经存放有元素
3.1 如果没有则直接加入
3.2 如果有，则调用equals()比较，如果相同就放弃添加；如果不相同则添加到最后
-
在jdk8中，如果一条链表的元素个数 >= TREEIFY_THRESHOLD （默认为8），并且table数组的大小 >= MIN_TREEIFY_CAPACITY （默认为64）就会进行树化（红黑树），否则仍然采用数组扩容机制
出处：https://www.cnblogs.com/liyuelian/p/16617881.html
