java集合初探（一）：HashMap.
一、概述
HashMap可能是我们最经常用的Map接口的实现了。话不多说，我们先看看HashMap类的注释：
基于哈希表的Map接口实现。
这个实现提供了所有可选的映射操作，并允许空值和空键。（HashMap类与Hashtable大致相当，只是它是不同步的，并且允许为null）
这个类对映射的顺序不做任何保证；特别是，它不保证顺序将随着时间的推移保持不变。
这个实现为基本操作（get和put）提供了恒定的时间性能，假设hash函数在bucket中适当地分散了元素。集合视图上的迭代所需的时间与HashMap实例的“容量”（bucket的数量）加上其大小（键值映射的数量）成比例。因此，如果迭代性能很重要，那么不要将初始容量设置得太高（或者负载系数太低），这一点非常重要。
HashMap的实例有两个影响其性能的参数：初始容量和负载因子。capacity是哈希表中的bucket数，初始容量就是创建哈希表时的容量。加载因子是一个度量哈希表在容量自动增加之前可以达到的完整程度。当哈希表中的条目数超过加载因子与当前容量的乘积时，哈希表将重新哈希（即重建内部数据结构），使哈希表的存储桶数大约为原来的两倍。
一般来说，默认的负载系数（.75）在时间和空间成本之间提供了很好的折衷。较高的值会减少空间开销，但会增加查找开销（反映在HashMap类的大多数操作中，包括get和put）。在设置初始容量时，应考虑地图中的预期条目数及其荷载系数，以尽量减少再灰化操作的次数。如果初始容量大于最大入口数除以负载系数，则不会发生再吹灰操作。
如果要在一个HashMap实例中存储许多映射，那么以足够大的容量创建它将使映射的存储效率更高，而不是让它根据需要执行自动重新缓存以增加表。请注意，使用具有相同hashCode（）的多个键肯定会降低任何哈希表的性能。为了改善影响，当键是可比较的时，这个类可以使用键之间的比较顺序来帮助打破联系。
请注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，并且至少有一个线程在结构上修改了该映射，则它必须在外部同步。（结构修改是指添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键相关联的值不是结构修改。）这通常是通过对自然封装映射的对象进行同步来完成的。如果不存在这样的对象，则应该使用集合.synchronizedMap方法。最好在创建时执行此操作，以防止意外的不同步访问映射：
Map m = Collections.synchronizedMap(new HashMap(...));注意，迭代器的fail-fast行为不能得到保证，因为一般来说，在存在不同步的并发修改时，不可能做出任何明确保证。Fail fast迭代器在尽最大努力的基础上抛出ConcurrentModificationException。因此，编写一个依赖这个异常来保证其正确性的程序是错误的：迭代器的fail-fast行为应该只用于检测bug。
以下是HashMap的类关系：
HashMap实现了Map接口，并继承 AbstractMap 抽象类，其中 Map 接口定义了键值映射规则。和 AbstractCollection抽象类在 Collection 族的作用类似， AbstractMap 抽象类提供了 Map 接口的骨干实现，以最大限度地减少实现Map接口所需的工作。
对于HashMap，我们关注六个问题：
- HashMap的数据结构（实现结构，什么情况变红黑树，树化和链化的阈值）
- HashMap构造函数（四个构造函数）
- HashMap的put（哈希、异或与或运算获取下标，为什么初始容量是2的n次方）
- HashMap的get（为什么重写equals方法需同时重写hashCode方法）
- HashMap的扩容（JDK8为什么不需要重哈希）
- HashMap为什么是线程不安全的？（1.7死循环，1.8数据覆盖）
二、HashMap的数据结构
1.底层实现
既然HashMap叫这个名字，那他的实现必然是基于哈希表的，关于哈希表我在数据结构与算法（十）：哈希表已有介绍。简而言之，哈希表就是一种结合数组与链表的一种数据结构，借助哈希算法快速获取元素下标以实现高效查找。
关于HashMap的底层的数据结构，我们需要了解两个成员变量以及一个内部类：
transient Node<K,V>[] table;：桶容器Node<K,V>：entrySet使用的，基于Map.Entry<K,V>接口实现的节点类，也就是同容器中的链表
画图描述一下就是：
我们知道哈希表解决哈希冲突的方式有开放地址法和分离链表法，这里很明显使用的是分离链表法，也就是俗称的拉链法。
当我们存储一个键值对的时候，会通过哈希算法获得key对应的哈希值，通过哈希值去找到在桶中要存放的位置的下标，而有时候不同的key会计算出相同的哈希值，也就是哈希碰撞，那么节点就会接在第一个节点的身后形成一条链表。当查找的时候先通过key计算得到哈希值找到链表，然后再遍历链表找到key，因此如果哈希碰撞严重，会导致链表变的很长，会影响到查找效率。
按这角度思考，如果桶数组很大，那么同样的哈希算法能得到的位置就更多，换句话说就是发生哈希碰撞的概率就越小，但是过大的桶数组又会浪费空间，所以就后面提到的扩容算法来动态的调整容量。
2.什么时候转为红黑树？为什么？
另外，我们知道在JDK7中HashMap底层实现只是数组+链表，而到了JDK8就变成了数组+链表+红黑树。
红黑树是一种复杂的树结构，这里我们简单的理解为一种具有二叉排序树性质和一定平衡二叉树性质（不要求绝对平衡以避免频繁旋转）的二叉树。
我们知道发生哈希碰撞的节点会在桶中形成链表，而当链表上的元素超过8个的时候就会转变成红黑树。这是因为同样深度的情况下，树可以储存比链表更多的元素，并且同时能保证良好的插入删除和查找效率。当元素小于6个的时候又会转回链表。
那么为什么会选择8和6这两个数字呢？
-
效率问题：
红黑树的平均查找长度是lg(n)，而链表是n/2。按这个计算，lg(8)=3，6/2=3 -> lg(4)=2， 4/2=2，我们可以看见当越小于8的时候红黑树和链表查找效率就越差不多，加上转化为红黑树还需要消耗额外的时间和空间的情况下，所以不如直接用链表。
-
防止频繁的转换：
8和6之间隔了一个7，如果转换为树和转换为链表的阈值是直接相邻，那么很可能出现频繁在树和链表的结构件转换的现象。
三、HashMap的构造函数
我们先来看看有关HashMap构建中可能涉及的成员变量：
-
transient int size：实际存储的key-value键值对的个数； -
int threshold：要调整大小的下一个大小值。一般是容量 * 负载系数，但是构造函数执行后大小等于初始化容量，只有第一次添加元素后才会初始化；
-
final float loadFactor：负载因子，代表了table的填充度有多少，默认是0.75。加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。 所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32；
-
transient int modCount：HashMap被改变的次数。由于HashMap非线程安全，在对HashMap进行迭代时， 如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作）， 需要抛出异常ConcurrentModificationException
1.有初始容量和负载因子的构造方法
构造一个具有指定初始容量和负载因子的空HashMap。
这里提到的负载因子，负载因子衡量的是一个散列表的空间的使用程度。
public HashMap(int initialCapacity, float loadFactor) {
//初始容量必须大于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能大于最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//初始化加载因子
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
这里调用的tableSizeFor()方法是个位运算，他的作用是：
对于给定的目标容量，返回2的幂
换而言之，初始化容量必须是2的n次方，这个地方与HashMap如何向集合高效添加元素的需求是直接相关的。
具体的分析可以参考：HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）。
接着我们可以看到初始容量处理后直接给了threshold，不直接使用initialCapacity而是这样做的原因是一开始的时候map的底层容器table尚未初始化，这个操作被放到了第一次put上，所以当我们第一次添加元素的时候，才会根据指定的初始大小去初始化容器。
2.只有初始容量的构造方法
构造一个具有指定初始容量和默认负载因子（0.75）的空HashMap。
public HashMap(int initialCapacity) {
//直接调用 HashMap(int initialCapacity, float loadFactor)构造方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3.无参构造方法
构造一个具有指定初始容量（16）和默认负载因子（0.75）的空HashMap。
public HashMap() {
//全部使用默认值
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
4、有一个Map类型的参数的构造方法
使用与指定Map相同的映射构造一个新的HashMap。使用默认的负载因子（0.75）和足以将映射保存在指定Map中的初始容量创建HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
这里调用了putMapEntries()方法，我们待会再细说，现在先简单里理解为根据一个已经存在的Map集合去创建一个新Map集合，有点类似于Arrays.copyOf()方法。
四、HashMap的put
我们从上文可以知道，当构造函数执行完毕以后，并没有真正的开辟HashMap的数据存储空间，而是等到第一次put的时候才会为table分配空间。
1.put操作的实现
HashMap中有一个put()方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
它的注释是这样描述的：
将指定值与该映射中的指定键相关联。如果该映射先前包含该键的映射，则将替换旧值。
简单的来说，就是两个功能：
- 将值与建关联
- 如果新值对应的键已有旧值，则替换旧值
我们可以看到，实际上这个方法通过hash（）和putVal() 两个方法来实现。
2.计算桶容器下标
桶容器下标通过三个步骤来计算：获取哈希值，异或运算混合高低位得到新哈希，新哈希和长度与运算获取下标。
我们看看hash()方法的源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里的hashCode()方法是一个Native方法，原理是将对象的内存地址转为一个整数以获取对象哈希值。
这一个方法先调用了一个 key.hashCode()方法获取了key的哈希值，然后将哈希值与哈希值的高16位做异或运算。
而在下面的putVal()方法中，又通过类似下面三行代码进行取模：
//n为新桶数组长度
n = (tab = resize()).length;
//进行与运算取模
(n - 1) & hash
从网上看到一张很形象的图：
我们来理解一下：
-
我们先看与运算取模。一方面位与运算运算快；另一方面由于长度必然是2的幂，所以转二进制有效位必然全是1，与运算的时候可以充分散列表。
-
异或运算混合高低位：为了将哈希值的高位和低位混合，以增加随机性。
比如数组table的长度比较小的时候（比如图中的长度就只有4），也能保证考虑到哈希值的高低位都参与计算中。
为了更明确的说明长度取2的幂有助于充分散列避免哈希碰撞，这里举个特别明显的例子：
当HashMap的容量是16时，它的二进制是10000，(n-1)的二进制是01111，与hash值得计算结果如下：
上面四种情况我们可以看出，不同的hash值，和(n-1)进行位运算后，能够得出不同的值，使得添加的元素能够均匀分布在集合中不同的位置上，避免hash碰撞。
下面就来看一下HashMap的容量不是2的n次幂的情况，当容量为10时，二进制为01010，(n-1)的二进制是01001，向里面添加同样的元素，结果为：
可以看出，有三个不同的元素进过&运算得出了同样的结果（01001），严重的hash碰撞了。
3.将元素加入桶数组
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[i]是否为空或为null，否则执行resize()进行扩容
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);
//插入后链表长度大于8就转换成红黑树
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的get
1.get操作的实现
我们看看get()方法的注释和源码：
返回指定键所映射到的值；如果此映射不包含键的映射关系，则返回null。更正式地讲，如果此映射包含从键k到值v的映射，使得（key == null？k == null：key.equals（k）），则此方法返回v；否则，返回v。否则返回null。 （最多可以有一个这样的映射。）返回值null不一定表示该映射不包含该键的映射；它的返回值为0。映射也可能将键显式映射为null。 containsKey操作可用于区分这两种情况。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
我们可以看到实际上调用了getNode()方法：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//确保table不为空，并且计算得到的下标对应table的位置上有节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断第一个节点是不是要找的key
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果第一个节点就查找链表或者红黑树
if ((e = first.next) != null) {
//红黑树上查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//链表上查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2.为什么重写equals还要重写hashcode？
首先，不被原本的的hashCode和equals是这样的
- hashCode值是根据内存地址换算出来的一个值
- equals方法是判断两个对象内存地址是否相等
我们回顾一下上文，可以看到无论put()还是get()都会有类似这样的语句：
p.hash == hash && (key != null && key.equals(k))
当我们试图添加或者找到一个key的时候，方法会去判断哈希值是否相等和值是否相等，都相等的时候才会判断这个key就是要获取的key。也就是说，严格意义上，一个HashMap里是不允许出现相同的key的。
当我们使用对象作为key的时候，根据原本的hashCode和equals仍然能保证key的唯一性。但是当我们重写了equals方法而不重写hashCode()方法时，可能出现值相等但是因为地址不相等导致哈希值不同，最后导致出现两个相同的key的情况。
我们举个例子：
我们现在有一个类：
/**
* @Author：CreateSequence
* @Date：2020-08-14 16:15
* @Description：Student类，重写了equals方法
*/
public class Student {
String name;
Integer age;
/**
* 重写了equals方法
* @param obj
* @return
*/
@Override
public boolean equals(Object obj) {
Student student = (Student) obj;
return (this.name == student.name) && (this.age == student.age);
}
public Student(String name, Integer age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
然后我们试试看：
public static void main( String[] args ) {
HashMap<Student,Integer> map = new HashMap(16);
Student student1 = new Student("小明", 21);
map.put(student1, 1);
Student student2 = new Student("小明", 21);
System.out.println("这个key已经存在了吗？"+map.containsKey(student2));
System.out.println(map.get(student2));
}
//输出结果
这个key已经存在了吗？false
null
可以看到，因为hashCode()得到的值不同，在map中他们被当成了不同的key。
而当我们重写了Student类的hashCode()方法以后：
@Override
public int hashCode() {
return age;
}
执行结果就变成：
这个key已经存在了吗？true
1
可见重写equals还要重写hashcode的必要性。
参考：
六、HashMap的扩容
1.resize操作的实现
话不多说，我们直接源码
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;
//哈希值与原长度进行与运算，如果多出来那一位是0，就保持原下标
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果多出来那一位是1，就移动到（原下标+原长度）对应的新位置
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;
}
2.为什么JDK8不需要重哈希了？
我们知道，如果桶数组扩容了，那么数组长度也就变了，那么put和get的时候根据长度与哈希进行与运算的时候计算出来的下标就不一样。在JDK7扩容移动旧容器的数据的时候，会进行重哈希获得新索引，而在JDK8进行了优化。
因为桶数组长度总是2的幂，所以扩容以后翻倍，转换为二进制的时候就会比原来多一位，如果我们假设桶数组为n，则有：
n = 16 -> 10000; (n-1) - > 1111;
n = 32 -> 100000; (n-1) - > 11111;
n = 64 -> 1000000; (n-1) - > 111111;
n = 128 -> 10000000; (n-1) - > 1111111;
我们举例子验证一下，如下图：
（a）是n=16时，key1与key2跟（n-1）与运算得到的二进制下标；（b）是扩容后n=32时，key1与key2跟（n-1）与运算得到的二进制下标。
我们可以看到key2进了一位，多出来这一位相当于多了10000，转为十进制就是在原基础上加16，也就是加上了原桶数组的长度，反映到代码里，就是 newTab[j + oldCap] = hiHead;这一句代码；
现在在看看key1，我们看到key1的索引并没有移动，因为key多出来的那一位是0，所以与运算后还是0，最后得到的下标跟原来的一样。
所以我们可以总结一下：
- 哈希值与原长度（注意是n不是n-1）进行与运算，判断多出来的那一位是0还是1
- 如果是0就留在原来的位置
- 如果是1就移动到（原下标 + 原长度）对应下标的新位置
这样做的好处除了不需要重新计算哈希值以外；由于哈希值多处来的一位数可能是0也可能是1，这样就让原本在同一条链表的上元素有可能可以在扩容后移动到新位置，有效缓解了哈希碰撞。
七、HashMap线程不安全
我们知道HashMap是线程不安全的，线程安全的Map集合是ConcurrentHashMap。事实上，HashMap的线程不安全在JDK7和JDK8表现不同：
- 在JDK7因为resize过程使用了头插法，导致多线程环境下可能会产生死循环，数据覆盖和数据丢失等问题
- JDK8解决了死循环问题，但是在扩后的添加中仍然会在多线程环境下出现数据覆盖的问题
1.JDK7头插法导致死循环
在JDK7中，错误出现在扩容方法transfer中，其代码如下：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//遍历链表，当前节点为e
while(null != e) {
//获取当前节点的下一个节点next
Entry<K,V> next = e.next;
//重新计算哈希值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity
//头插法
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
从代码中我们可以看到，扩容后重新计算了元素的下标，并采用头插法将表元素移插到新链表上。
举个例子：
假设线程A线程B同时对下图集合扩容：
1.A先执行，在newTable[i] = e前时间片耗尽被挂起，此时e = 1，e.next = null，next = 2
2.线程B执行数组扩容，扩容完以后对于线程A就是现在这样，此时next.next = 1，e.next = null，next = 2：
3.接着线程B挂起，线程A继续执行 newTable[i] = e以后的代码，执行完毕后e = 2，next = 2，e.next = 1：
4.线程A接着下一次循环，由于e.next = 1，于是next = 1，头插法把2插入newTable[i]中，执行完毕以后e = 1，next = e.next = null：
5.线程A执行最后一次循环，此时由于e.next = newTable[i]，所以e.next = 2，然后接着 newTable[i] = e ，也就是说1又被插回newTable[i]的位置：
这个时候最危险的事情发生了：e = 1，e.next =2 ，e.next.next = 1，说明2和1已经形成了一个环形链表：
在此之后会无线循环1和2的头插，造成死循环。
2.JDK8数据覆盖
DK7中也有这个问题。
我们知道put()方法在插入时会对插入位置进行非空判断，如果两个线程都判断同一个位置为空，那么先执行插入的数据就会被后一个覆盖。
