3. HashMap
参考其他博主 + 自己总结
3.1 什么是HashMap
- HashMap继承了AbstractMap，实现了Map接口，存储的是一个键值对对象。
- 底层结构 数组+链表+红黑树，可以存储null键null值，线程不安全
- 初始size为16，扩容：newSize = oldSize * 2，size一定为2的n次幂（元素分配更均匀）
- 计算index方法：index = hash & (tab.length – 1)
3.2 HashMap数据结构解析
1、继承关系：
HashMap继承了AbstractMap，实现了Map接口。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
}
2、常量及构造方法
//这两个是限定值 当节点数大于8时会转为红黑树存储
static final int TREEIFY_THRESHOLD = 8;
//当节点数小于6时会转为单向链表存储
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树最小长度为 64
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap容量初始大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap容量极限
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Node是Map.Entry接口的实现类
//在此存储数据的Node数组容量是2次幂
//每一个Node本质都是一个单向链表
transient Node<K,V>[] table;
transient int size; //HashMap大小,它代表HashMap保存的键值对的多少
transient int modCount; //HashMap被改变的次数
int threshold; //扩容阈值，当 HashMap 的个数达到该值，触发扩容
final float loadFactor; //存储负载因子的常量。负载因子，扩容阈值 = 容量 * 负载因子。
static class Node<K,V> implements Map.Entry<K,V> {...}
//默认的构造函数：造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定容量大小：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//指定容量大小和负载因子大小：构造一个带指定初始容量和加载因子的空 HashMap
public HashMap(int initialCapacity, float loadFactor) {
//指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判定指定的容量大小是否大于HashMap的容量极限
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//指定的负载因子不可以小于0或为Null，若判定成立则抛出IllegalArgumentException异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
this.threshold = tableSizeFor(initialCapacity);
}
//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//此构造方法主要实现了Map.putAll()
putMapEntries(m, false);
}
【问题1】为什么要改成“数组+链表+红黑树”？
- 主要是为了提升在 hash 冲突严重时（链表过长）的查找性能
- 使用链表的查找性能是 O(n)
- 使用红黑树是 O(logn)
【问题2】那在什么时候用链表？什么时候用红黑树？
-
对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。
table长度小于常量MIN_TREEIFY_CAPACITY时，不会变为红黑树
两个限制条件：
- 同一个位置的节点数 > 8
- hashMap的总长度 >= 64
对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。
static final int TREEIFY_THRESHOLD = 8; //这两个是限定值 当节点数大于8时会转为红黑树存储
static final int UNTREEIFY_THRESHOLD = 6; //当节点数小于6时会转为单向链表存储
static final int MIN_TREEIFY_CAPACITY = 64; //红黑树最小长度为 64
【问题3】那为什么转回链表节点是用的6而不是复用8？
如果我们设置节点多于8个转红黑树，少于8个就马上转链表，当节点个数在8徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗。
3、数据结构
HashMap在JDK1.8之前的实现方式是数组+链表，但是JDK1.8对HashMap进行了底层优化，改为由 数组+链表+红黑树实现，主要目的是提高查询效率。
数组的索引是根据key的hash值计算得到的，不同的hash值有可能产生一样的索引，这就是哈希冲突，此时可采用链地址法处理哈希冲突，即将所有索引一致的节点构成一个单链表。
- jdk1.8 中使用一个 Node 数组来存储数据，但这个 Node 可能是链表结构，也可能是红黑树结构
- 如果插入的 key 的 hashcode 相同，那么这些key也会被定位到 Node 数组的同个格子里
- 如果同一个格子里的key不超过8个（默认阀值），使用链表结构存储
- 如果超过了8个（且数组长度大于等于64）那么会调用 treeifyBin 函数，将链表转换为红黑树
- 那么即使 hashcode 完全相同，由于红黑树的特点，查找某个特定元素，也只需要O(log n)的开销也就是说put/get的操作的时间复杂度最差只有 O(log n)
3. 2-1 HashMap的插入原理
- 判断数组是否为空，为空进行初始化;
- 不为空，计算 key 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
- 查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
- 存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
- 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)
- 如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8并且数组长度大于64， 大于的话链表转换为红黑树；
- 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍
【问题1】hash函数设计
获取key的hashcode，hashcode是一个32位的int型值
hash = hashcode的高16位和低16位进行异或操作（^）（相同为0，不同为1）。
确定元素在数组位置下标：index = hash & (n - 1)
优点：
-
减少hash冲突。（为什么要将 hashCode 的高16位参与运算？）
因为key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围为-2147483648~2147483647 ，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。（不能直接用key的hashcode）即使散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。
主要是为了在 table 的长度较小的时候，让高位也参与运算，并且不会有太大的开销。如果不加入高位运算，由于 n - 1 是 0000 0111，所以结果只取决于 hash 值的低3位，无论高位怎么变化，结果都是一样的。如果我们将高位参与运算，则索引计算结果就不会仅取决于低位。
-
确定元素在数组位置下标：index = hash & (n - 1)
- 当 n 为 2 的 N 次方时，n - 1 为低位全是 1 的值，此时任何值跟 n - 1 进行 & 运算的结果为该值的低 N 位，达到了和取模同样的效果，实现了均匀分布。
- 位运算比取余%运算要快。
计算索引位置的公式为：(n - 1) & hash，当 n 为 2 的 N 次方时，n - 1 为低位全是 1 的值，此时任何值跟 n - 1 进行 & 运算的结果为该值的低 N 位，达到了和取模同样的效果，实现了均匀分布。实际上，这个设计就是基于公式：x mod 2^n = x & (2^n - 1)，因为 & 运算比 mod 具有更高的效率。
3.2-2 HashMap的初始化
无参构造器new hashMap()不传值，默认大小是16，负载因子是0.75
有参构造器根据传入的的初始大小k，初始化map的大小为大于等于k的2的整数次方。eg：k = 10-----> n = 16;
HashMap的大小必须是2的整数次方。
3.3 HashMap中hashCode的作用
快速查找
因为需要它来对HashMap的数组位置来定位，如果HashMap里存一个数，单纯依次使用equals方法比较key是否相同来确定当前数据是否已存储，效率会很低，通过比较hashCode值，效率会大大提高。
3.4 HashMap的数组长度为什么是2的n次幂
- 计算索引位置的公式为：(n - 1) & hash
- 当n为2^n的时候----均匀分布
- 当n不是2^n的时候----数组元素分组不均匀，有一些位置可能永远用不到，数组利用率低且运算结果碰撞率高
计算索引位置的公式为：(n - 1) & hash
当 n 为 2 的 N 次方时，n - 1 为低位全是 1 的值，此时任何值跟 n - 1 进行 & 运算的结果为该值的低 N 位，达到了和取模同样的效果，实现了均匀分布。实际上，这个设计就是基于公式：x mod 2^n = x & (2^n - 1)，因为 & 运算比 mod 运算具有更高的效率。
HashMap的put（）方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
然后再点进putVal 方法，则会看到其中有下面的代码：
tab[i = (n - 1) & hash]
当数组长度不为2的n次幂 的时候，hashCode 值与数组长度减一做与运算的时候，会出现重复的数据，因为不为2的n次幂 的话，对应的二进制数肯定有一位为0 ,这样，不管你的hashCode 值对应的该位，是0 还是1 ,最终得到的该位上的数肯定是0 ，这带来的问题就是HashMap 上的数组元素分布不均匀，而数组上的某些位置，永远也用不到。这将带来的问题就是你的HashMap 数组的利用率太低，并且链表可能因为上边的(n - 1) & hash 运算结果碰撞率过高，导致链表太深。（当然jdk 1.8已经在链表数据超过8个以后转换成了红黑树的操作，但那样也很容易造成它们之间的转换时机的提前到来）。
所以说，当数组长度为2的n次幂的时候，数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
3.5 HashMap何时扩容以及它的扩容机制？
- 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
-
ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。
- 长度n改变，hash= hashcode的高16位和低16位进行异或操作（^）（不变）---->index = (n - 1) & hash 也会改变
- 正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要么就相同，要么就是新下标等于旧下标加上旧数组的长度*。
何时进行扩容？
HashMap使用的是懒加载，构造完HashMap对象后，进行put 方法插入元素之前，HashMap并不会去初始化或者扩容table。当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化， 当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
具体是什么时候呢 ：
当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16 * 0.75=12的时候，就把数组的大小扩展为 216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。*
【问题1】刚才说的负载因子默认初始值又是多少？
负载因子默认值是0.75。
【问题2】为什么是0.75而不是其他的？
这个也是在时间和空间上权衡的结果。
- 如果值较高，例如1，此时会减少空间开销，但是 hash 冲突的概率会增大，增加查找成本
- 如果值较低，例如 0.5 ，此时 hash 冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。
【问题4】为什么要将 hashCode 的高16位参与运算？
主要是为了在 table 的长度较小的时候，让高位也参与运算，并且不会有太大的开销。
例如下图，如果不加入高位运算，由于 n - 1 是 0000 0111，所以结果只取决于 hash 值的低3位，无论高位怎么变化，结果都是一样的。
如果我们将高位参与运算，则索引计算结果就不会仅取决于低位。
3.6 HashMap是线程安全的吗？如何实现线程安全？
HashMap不是线程安全的， 如果多个线程同时检测到元素的个数超过阀值(数组大小*负载因子)，多个进程会同时对Node数组进行扩容,都在重新计算元素位置以及复制数据,但是最终只有一个线程扩容后的数组会赋给table,其他线程的都会丢失,并且各自线程put的数据也丢失。
实现线程安全的方式：
使用HashTable：HashTable使用synchronized来保证线程安全，但是所有线程竞争同一把锁，效率低
ConcurrentHashMap：使用锁分段技术，将数据分段存储，给每一段数据配一把锁，效率高。 Java8中使用CAS算法（了解CAS算法请参考 Java并发编程之原子变量和CAS算法）
SynchronizedMap： 调用synchronizedMap()方法后会返回一个SynchronizedMa类的对象,而在
SynchronizedMap类中使用了synchronized同步关键字来保证对Map的操作是安全的。
3.7 HashMap的实现原理及它与HashTable、 ConcurrentHashMap的区别
HashMap
- 底层结构 数组+链表+红黑树，可以存储null键null值，线程不安全；
- 初始size为16，扩容：newSize = oldSize * 2，size一定为2的n次幂（元素分配更均匀）,负载因子默认大小 0.75
- 计算index方法：index = hash & (tab.length – 1)
HashTable
底层结构 数组+链表，无论是key还是value都不能为null，线程安全（很多方法都是加了synchronized关键字的）。实现线程安全的方式是在修改数据时锁住整个hashTable，效率低，ConcurrentHashMap做了相关优化。
初始size为11，扩容：newSize = oldSize * 2 + 1, 负载因子默认大小 0.75
int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;实现原理和HashMap类似
ConcurrentHashMap
- 底层结构 数组+链表，线程安全，效率高
- 通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。
- Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分段技术
- 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
- 扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容
拓展：
锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表，从而在同一时刻只能由一个线程对其进行操作；而ConcurrentHashMap中则是一次锁住一个桶。
ConcurrentHashMap默认将hash表分为16个桶，诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。
一些讲得不错的HashMap的博客：
面试阿里，HashMap 这一篇就够了
HashMap 常见问题Java8(扩容、转红黑树、退化链表、Hash优化)
