JDK 1.8 对HashMap做了很大的优化，底层实现从“数组+链表”，改成了“数组+链表+红黑树”。
简单来说，当发生哈希冲突时，节点会以链表的形式增加在table数组的索引上。如果链表超过一定长度，就会转成红黑树。
转成红黑树后，链表的结构依然存在，只不过会选择使用红黑树的结构来查找节点。红黑树的每次操作都会维护链表的结构。
Map 取代了古老的 Dictionary 抽象类。
map是用于存储键值对<key, value>的集合类
键用Set类型的KeySet存储，值用Collection类型的Values存储。
每个键值对都是一个Entry类型的数据。
HashMap的亮点：
（2）成员变量
常量
可以看出一些HashMap的设计思想：
普通成员变量
此外，HashMap还包含一个普通链表节点类
这就是HashMap的单链表基本存储单元，有四个属性：hash、key、value、next
其中key是final的，意味着创建对象后key不能被修改。
hash也是final的，它由有参构造从外部指定，在节点类没有计算hash的方法。
这个hash缓存的是key的hashCode（经过扰动的），用于在插入节点时快速获得当前节点的hash值重写了两个方法：
针对key和value分别求hashCode，然后进行异或运算，结果作为当前节点的hashCode。
一个红黑树节点类
有三种有参构造器，一种无参构造器：
有参构造之间是相互调用的关系
Float.isNaN：如果指定的值不是数字，就返回true
可以看出：
此时的扩容阈值threshold不是真正的阈值，而是代表首次初始化的数组的长度，后面会重新计算。它的作用是，根据我们传入的容量，计算一个大于等于该容量的最小的2的N次方。比如传入7，会返回8；传入9，会返回16
这个公式会通过最高位的1，得到2个、4个、8个1...具体取决于高位有多高。
经过这5次运算后，会得到一个低位全是1的值，在返回时+1，就能得到1个比n大的2的N次幂。
开头的cap -1，是为了防止cap本身就是2的N次幂的情况。
HashMap中计算数组下标的步骤：
调用hash()
获得key的hashCode()，和它的高16位做异或运算，将结果作为哈希值
hash方法（扰动函数，目的是在哈希函数的基础上，进一步降低哈希冲突）
计算一个键的哈希值，具体做法：
HashMap如何通过哈希函数定位数组索引
hash值的范围是int的范围，有40亿长度，但不可能创建一个这么长的数组，所以要对数组长度做取模运算，把哈希值映射到数组的索引上。
源码的取模运算部分：
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;将计算出来的 hash 值与 (table.length - 1) 进行 & 运算，而不是常见的取模运算。
取模运算消耗较大，计算机中最快的是位运算。JDK团队做了优化，用位运算替代了取模运算，达到一样的效果。
这是根据公式：x mod 2^n = x & (2^n - 1)
HashMap底层数组的长度规定必须是2的n次方，取模运算为 “h mod table.length”，对应上面的公式
可以得到该运算等同于“h & (table.length - 1)”
这就是HashMap规定，table容量必须为2的N次幂的原因，目的是优化取模运算。
这种做法可以保证，得到的索引一定小于数组的长度
为什么哈希函数特殊设计成，要将hashCode右移16位参与运算？
将 hashCode 的高 16 位与 hashCode 进行异或运算，主要是为了在 table 的 length 较小的时候，让hashCode的高位也参与运算，降低哈希冲突的概率，并且不会有太大的开销。
在length较小时，它的高位都是0，只有低位有少量的1，只有这些1和hashCode的低位进行了运算，得到了最终的索引把高位也利用起来，让hash值的低位获得更多的1。异或的规则是，相同则0，否则为1。所以可以把hashCode右移，让它的1错开，然后通过异或运算，获得更多的1，进而获得更大范围的hashCode，进而减小哈希冲突的概率。
使用无符号右移16位，是因为HashCode有32位，正好把前半部分和后半部分错开，获得所有的1。
因为对于同样的键，HashCode是唯一的，所以采取这种算法，也能保证得到的hashCode是唯一的。
为什么用异或，不用或运算
如果单纯为了利用所有的1，那使用或运算更好，能保留全部的1
但是这样没有意义，因为会大大增加hash冲突的概率
而异或就比较好，又能提供高位的1，又保留了hash的多样性。
在HashMap中存入一个值，需要做这些事情：
如果table数组尚未初始化，调用resize进行初始化
根据传入的key和value构建Node对象
计算节点的hash值，即节点的存储索引
将节点存储到该索引上的链表或红黑树上
扩容机制
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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}主要做的事情：
注意：
有两种使用情况：
做的事情可以分为两个各部分：
HashMap链表节点重hash的优化机制
这是JDK1.8的特性，JDK1.7之前还是使用的重hash策略。
由于HashMap的表长度一定是2的N次幂，则表长度扩容到2倍后，表长度只是多了一个二进制位。
一个Key的hash值 = 扰动后的hashcode & （表长度-1）。
hashcode 是不变的，表长度左移了一位，说明表长度的高位多了一位。hashMap的表长度有一个特点：肯定是2的幂。2的幂的特点是，高位是1，其他位都是0。
导致参与计算的hashcode值也多了一位，这个可能是0，可能是1。
将hashcode 和旧表的长度做与运算。之前的hash值是通过 表长度-1 计算出的，现在直接用表长度运算，hashcode的高一位会被利用上。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = 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;
}做的事情可以分为两个各部分：
将新的容量设置成原先的两倍（通过位运算）。如果此时的新容量小于最大容量，而且旧的容量大于默认容量16，就将扩容阈值设置为原先的两倍。如果结果为0，说明hashcode的高一位是0，那么如果和新表长度-1进行与运算，对应位的值肯定为0。后面的值，新表和旧表进行运算时后面都是1，所以后面的位不变。所以新的索引等于 旧的索引，不变。
如果结果为1，说明hashcode的高一位是1，那么如果和新表长度-1进行与运算，对应位的值肯定为1。后面的位不变，hash的结果只多了最高位的1。如果用这个高位的1，后面补0，和新表长度-1进行与运算，得到的值是旧表的长度。所以新的索引等于 原先的表长 + 旧索引。
HashMap链表节点重hash的优化机制
这是JDK1.8的特性，JDK1.7之前还是使用的重hash策略。
由于HashMap的表长度一定是2的N次幂，则表长度扩容到2倍后，表长度只是多了一个二进制位。
一个Key的hash值 = 扰动后的hashcode & （表长度-1）。
hashcode 是不变的，表长度左移了一位，说明表长度的高位多了一位。hashMap的表长度有一个特点：肯定是2的幂。2的幂的特点是，高位是1，其他位都是0。
导致参与计算的hashcode值也多了一位，这个可能是0，可能是1。
将hashcode 和旧表的长度做与运算。之前的hash值是通过 表长度-1 计算出的，现在直接用表长度运算，hashcode的高一位会被利用上。
如果结果为0，说明hashcode的高一位是0，那么如果和新表长度-1进行与运算，对应位的值肯定为0。后面的值，新表和旧表进行运算时后面都是1，所以后面的位不变。所以新的索引等于 旧的索引，不变。
如果结果为1，说明hashcode的高一位是1，那么如果和新表长度-1进行与运算，对应位的值肯定为1。后面的位不变，hash的结果只多了最高位的1。如果用这个高位的1，后面补0，和新表长度-1进行与运算，得到的值是旧表的长度。所以新的索引等于 原先的表长 + 旧索引。
注意：JDK1.7中rehash时，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但JDK1.8没有这个问题。
这部分的源码，它会保存该节点的前一个节点和后一个节点，所以不会乱序。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}通过key，获取对应的value。
调用getNode方法，传入key的哈希值和key，获取节点对象
做的事情：
getTreeNode
红黑树的查找目标节点方法
首先找到红黑树的根节点
使用根节点调用find方法
removeNode()
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}做的事情可以分为两部分：
根据key查找到目标节点
删除目标节点
JDK 1.8是数组，解决哈希冲突的方案是链表+红黑树。
JDK 1.8之前是数组+链表
使用红黑树主要是为了提高在哈希冲突频繁时的查找性能，链表是O(n)，红黑树是O(logn)。
插入操作，默认会实例化一个链表节点，如果发生了哈希冲突，就进行判断：
此时，检查新增节点后链表的长度。如果超过阈值（默认为8），即链表长度大于等于9时，判断数组大小：
移除操作，当同一个索引上移除节点后，节点数量只有6个，且节点类型为红黑树节点，就转换成普通链表节点。
链表转红黑树阈值为8是时间和空间进行权量的结果。
红黑树的节点大小几乎是普通链表节点的两倍。在节点数量少时，红黑树带来的性能提升并不明显，作者认为没有必要因此浪费空间。
理想情况下，节点分布在数组格子内的概率遵循泊松分布，则链表长度达到8的概率是0.00000006，非常小。所以红黑树的转换不会非常频繁。而且，节点个数大于8，红黑树的效率优势也开始体现了。
红黑树转链表的阈值是6，而没有复用8，原因是如果设置成节点少于8就立刻转回链表，当节点个数在8、9徘徊时，就会频繁进行链表和红黑树的转换，造成无意义的性能损耗。
而且，数组长度必须大于才有机会将链表转为红黑树，在此之前会采用扩容+重哈希的操作。
每次扩容时，元素的位置会改变，所以不能保证某一时刻的某个数据在HashMap中的相对位置。
这是因为HashMap在计算数组下标时，对取模运算有特殊设计：
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;这样运算需要保证，table的容量是2的n次幂。
而且扩容重哈希时也做出了优化。
HashMap的每个数据都是一个Node节点类或TreeNode红黑树节点类，它们都带有final的key属性和hash属性，保证对象创建后key和hash不能修改。
在添加数据时，源码是这样设计的：
先比较目标节点的hash值，和当前数据的hash值是否相等。如果不相等，它们的key肯定不一样。如果相等，再进行下面的比较：
目标节点的key == 当前key，或key不为null时，利用equals()比较目标节点和当前的key。这是考虑到了key为null的情况。
所以，在key不为null时，会先比较hash值，而hash值和key的hashCode()有关。如果hash值相等，再去调用equals()比较。都相等，则证明这个key已经存在。
所以存储自定义对象时，需要一同重写hashCode()和equlas()。
进一步分析：
在Object类中，对equals()方法的初始定义：
可以看出，如果不对equals进行修改，那么底层就是直接调用的 ==
所以源码这里这样设计，是两头都提供了用户自定义的比较方法，用户可以自己重写hashCode、也可以自己重写equals()。
完整的逻辑是：比较两个hash值是否相等，如果相等，再判断两个key是否==。如果不==的话，如果key不为null，调用equals()比较，如果返回true，则可以被看做同样的key。
具体到程序中，是通过哈希值找到了数组桶，再通过equals，在红黑树或链表上查找具体的节点。
在调用put()方法时，会调用hash()计算key的hash值，然后调用putVal()方法。
如果key为null，会直接返回0，不会调用hashCode()去计算。即HashMap的设计中，null的hash值是固定的0
所以null是可以作为key被存储的。存储位置比较特殊。
如果hash为0，则和任何数按位与 & ，结果都为0，所以key为null的值，存储空间一定在table[0]上
在JDK 1.8之前，一个新的节点插入链表，会取代原有的值，原来的值顺延到当前节点的后面。这么设计可能是因为设计者认为，新插入的值被使用到的概率比较高，将它放在链表的头部，可以更快地查找到它。
但头插法会带来一个问题：在多线程环境下，可能会产生环形链表，此时进行取值，就可能会造成死循环。
在插入时不会发生问题，但一旦发生扩容，就会进行一次重哈希，此时也是采用的头插法，会导致扩容前后链表顺序倒置，增加了原先节点的引用关系，形成环。
官方认为这不属于BUG，因为HashMap本就不是线程安全的，但权衡影响和设计后，JDK 1.8还是调整为了尾插法，这样就保证了扩容前后链表节点顺序不变，从而杜绝了环的可能。
不是。虽然不会产生死循环，但数据的读写方法都不是同步的，多线程下可能出现数据不一致问题，线程安全无法保证。
put()方法，在并发场景下，如果计算出的索引值相同，可能导致覆盖，进而丢失数据
get()方法，可能某个线程进行了put()，触发了扩容，那么线程2此时执行get()就可能导致获取值为null。
多线程环境下，一般都会使用HashTable或者ConcurrentHashMap。
但HashTable并发度低，处理方式也仅仅是在读写方法上同步锁，
所以通常会使用ConcurrentHashMap。
此外，还有一种方式：使用Collections.synchronizedMap(Map)创建线程安全的map集合，但并发度也比较低。
初始容量 = 预知数据量 / 加载因子
默认的加载因子是 0.75
思想是，能正好装进这些数据，保证不会发生扩容。
一般用Integer、String这种不可变类作为HashMap的Key。
容量不是2的整数次幂 还用&(length-1) 怎样？
容量是2的整数次幂，n -1 后，高位为1后的0都变为1，如 16：10000, 16-1=15：1111, 1111 再与 hash 做 & 运算的时候，各个位置的取值取决于 hash。
如果不是2的整数次幂，必然会有0的位，0与任何数&肯定为0，会增加哈希冲突的概率。
它的策略是，每次增加一个元素，就会检查当前元素个数是否超过扩容阈值，如果超过了就启动一次扩容。
这个扩容阈值是通过 当前最大容量 * 扩容因子 计算出来的。扩容因子可以在有参构造中指定，默认是0.75
扩容的策略
每次都会扩容成原先的2倍
容量上限是1>>30，如果容量超出了这个数，则不再增长，且阈值会被设置为 Integer.MAX_VALUE
新的扩容阈值也会被计算出来，也是 当前最大容量 * 扩容因子
扩容后负载因子是不变的
扩容后需要对所有的元素进行重hash，优化成了位运算。
这里遍历所有元素的方式是深度优先遍历，即顺着数组桶遍历，每次完整遍历一条链表或一颗红黑树
扩容的触发时机
懒分配数组空间：
新创建的HashMap，初始时数组没有分配空间。
如果是无参构造器创建的HashMap，只会指定负载因子为默认的0.75，不会指定容量，默认为16
如果是有参构造器创建的HashMap，可以指定负载因子，也可以指定集合的容量。
不过它并不是直接设置了集合的容量，而是先计算出大于指定容量的最小的2次幂，然后把这个结果设置为当前的扩容阈值
后续调用put()方法，如果当前Map的数组为空，就调用resize()方法进行数组的初始化。
在resize()方法中，如果数组为空或者数组长度为0，但是扩容阈值不为0，就会把扩容阈值作为新的数组长度，初始化数组。
扩充数组长度：
有三种方式：获取Entry的集合、获取key的集合、获取Value的集合。
获取map的entrySet，遍历entrySet，取出每一个entry，可以获取key和value
有两种遍历entrySet的方式：
增强for循环
Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
for(Map.Entry<Integer, Integer> entry : entrySet){
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}通过entrySet获取迭代器
Iterator<Map.Entry<Integer, Integer>> iterator = entrySet.iterator();
while (iterator.hasNext()) {
// 遍历时，需先获取entry，再分别获取key、value
Map.Entry entry = iterator.next();
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}获取key的Set集合
有两种遍历keySet的方式：
增强for循环
Set<Integer> keySet = map.keySet();
for(Integer key : keySet){
System.out.print(key);
System.out.println(map.get(key));
}通过keySet获取迭代器
Iterator<Integer> iterator1 = keySet.iterator();
Integer key = null;
while (iterator1.hasNext()) {
key = iterator1.next();
System.out.print(key);
System.out.println(map.get(key));
}获取value的Collection集合
有两种遍历Collection的方式：
增强for循环
Collection<Integer> values = map.values();
for (Integer value : values) {
System.out.println("value = " + value);
}通过Collection集合获取迭代器
Iterator<Integer> iterator2 = values.iterator();
while (iterator2.hasNext()){
System.out.println("iterator2 = " + iterator2);
}总结
在遍历Map集合时，推荐使用EntrySet的方式，效率比较高。
对于遍历KeySet，经历了两个过程：首先获得每一个key，然后再去map中通过key获取每一个value。
而对于遍历EntrySet，只需要经历一个过程：取出每个Entry对象的key和value即可。
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- how234.cn 版权所有 赣ICP备2023008801号-2
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务