HashMap
特点： HashMap的key和value都允许为空，无序的，且非线程安全的
数据结构： HashMap底层是一个数组，数组的每一项又都是链表，即数据和链表的结合体。当新建一个HashMap对象时，就会初始化一个数组
1 static class Entry<K,V> implements Map.Entry<K,V> {
2 final K key;
3 V value;
4 Entry<K,V> next;
5 int hash;
6 ...
7 }
HashMap的存储单元Entry里面存放键值，且它持有指向下一个元素的引用，从而构成了链表
HashMap的存储
1 public V put(K key, V value) {
2 if (key == null)
3 return putForNullKey(value);
4 int hash = hash(key.hashCode());
5 int i = indexFor(hash, table.length);
6 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
7 Object k;
8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
9 V oldValue = e.value;
10 e.value = value;
11 e.recordAccess(this);
12 return oldValue;
13 }
14 }
15
16 modCount++;
17 addEntry(hash, key, value, i);
18 return null;
19 }
put()方法的步骤：
- 当key为空时，空的key会默认放在第零位的数组上
- 拿到key的hash值，再调用hash()方法重新计算出一个hash值。根据JDK源码，调用hash()方法的目的是为了打乱原有的hash值，防止糟糕的hash算法
1 static int hash(int h) {
2 h ^= (h >>> 20) ^ (h >>> 12);
3 return h ^ (h >>> 7) ^ (h >>> 4);
4 }
3. 根据hash值对Entry数组取模获得到存放数据的位置。取模操作的正确性依赖于数组的长度必须是2的N次幂。所有，在HashMap的构造函数中，如果指定HashMap初始大小为initialCapacity，如果initialCapacity不是2的N次幂，HashMap会算出大于initialCapacity的最小2的N次幂，作为Entry数组的初始大小
static int indexFor(int h, int length) {
return h & (length-1);
}
4. 判断是否存在相同的key，存在则将新的value存入，旧的返回，细节是先比较hash值，相同则再比较key，从而提高效率
5. modCount++是用于fail-fast机制，每次修改HashMap的数据结构都会自增一次
1 void addEntry(int hash, K key, V value, int bucketIndex) {
2 Entry<K,V> e = table[bucketIndex];
3 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
4 if (size++ >= threshold)
5 resize(2 * table.length);
6 }
6. 调用addEntry()方法。先设置一个变量e指向当前数组下标对象，再将键值放入新建的Entry对象里并将该对象赋给数组下标对象，且对象指向的下一个元素为旧的对象e。简单来说就是新建一个对象，将键值存入里面，并且将这个对象放在数组索引位置的第一个（即链头），它的下一个元素指向以前的第一个。
之后判断是否需要扩容，threshold为是否扩容的最大元素数目，当前HashMap的大小大于或等于该值时，就会进行扩容
threshold = (int)(capacity * loadFactor);
HashMap的读取
1 public V get(Object key) {
2 if (key == null)
3 return getForNullKey();
4 int hash = hash(key.hashCode());
5 for (Entry<K,V> e = table[indexFor(hash, table.length)];
6 e != null;
7 e = e.next) {
8 Object k;
9 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
10 return e.value;
11 }
12 return null;
13 }
简单来说就是通过key获取hash值，通过hash值获取数组下标，找到数组位置，将hash和key去比较是否相同
HashMap的删除
1 public V remove(Object key) {
2 Entry<K,V> e = removeEntryForKey(key);
3 return (e == null ? null : e.value);
4 }
1 final Entry<K,V> removeEntryForKey(Object key) {
2 int hash = (key == null) ? 0 : hash(key.hashCode());
3 int i = indexFor(hash, table.length);
4 Entry<K,V> prev = table[i];
5 Entry<K,V> e = prev;
6
7 while (e != null) {
8 Entry<K,V> next = e.next;
9 Object k;
10 if (e.hash == hash &&
11 ((k = e.key) == key || (key != null && key.equals(k)))) {
12 modCount++;
13 size--;
14 if (prev == e)
15 table[i] = next;
16 else
17 prev.next = next;
18 e.recordRemoval(this);
19 return e;
20 }
21 prev = e;
22 e = next;
23 }
24
25 return e;
26 }
- 通过key获取hash值，通过hash值获取数组下标，得到数组位置
- 遍历链表，找到匹配的。当删除的是链头，将数组下标指向下一个，如果删除的不是链头，则将前一个对象的next指向被删除的后一个
Fail-Fast机制
HashMap是线程不安全的，所以当使用迭代器的过程中，有其他线程修改了map，则会抛出ConcurrentModificationException，这就是fail-fast策略
modCount为修改次数，当HashMap内容修改都将增加这个值，在迭代器迭初始化过程中会将这个值赋给expectedModCount，在迭代的过程中判断这两个值是否相等，不相等则表示被其他线程修改了Map
1 final Entry<K,V> nextEntry() { 2 if (modCount != expectedModCount) 3 throw new ConcurrentModificationException();
注意： modCount使用volatile修饰，保证线程之间修改的可见性
HashMap(jdk1.8)
jdk1.8版本的HashMap底层是由数组，链表和红黑树实现的。底层的内部类由Entry变成了Node
1 static class Node<K,V> implements Map.Entry<K,V> {
2 final int hash;
3 final K key;
4 V value;
5 Node<K,V> next;
6
7 Node(int hash, K key, V value, Node<K,V> next) {
8 this.hash = hash;
9 this.key = key;
10 this.value = value;
11 this.next = next;
12 }
13
14 public final K getKey() { return key; }
15 public final V getValue() { return value; }
16 public final String toString() { return key + "=" + value; }
17
18 public final int hashCode() {
19 return Objects.hashCode(key) ^ Objects.hashCode(value);
20 }
21 ......
22 }
hash()方法也变了，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低位都参与到Hash的计算中，同时不会有太大的开销。
1 static final int hash(Object key) {
2 int h;
3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4 }
put()方法
上传个网上的图片，put()方法的流程
1 public V put(K key, V value) {
2 return putVal(hash(key), key, value, false, true);
3 }
4
5 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
6 boolean evict) {
7 Node<K,V>[] tab; Node<K,V> p; int n, i; 8 if ((tab = table) == null || (n = tab.length) == 0)//步骤①
9 n = (tab = resize()).length;
10 if ((p = tab[i = (n - 1) & hash]) == null)//步骤②
11 tab[i] = newNode(hash, key, value, null);
12 else {
13 Node<K,V> e; K k;
14 if (p.hash == hash && //步骤③
15 ((k = p.key) == key || (key != null && key.equals(k))))
16 e = p;
17 else if (p instanceof TreeNode) //步骤④
18 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
19 else {//步骤⑤
20 for (int binCount = 0; ; ++binCount) {
21 if ((e = p.next) == null) {
22 p.next = newNode(hash, key, value, null);
23 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
24 treeifyBin(tab, hash);
25 break;
26 }
27 if (e.hash == hash &&
28 ((k = e.key) == key || (key != null && key.equals(k))))
29 break;
30 p = e;
31 }
32 }
33 if (e != null) { // existing mapping for key
34 V oldValue = e.value;
35 if (!onlyIfAbsent || oldValue == null)
36 e.value = value;
37 afterNodeAccess(e);
38 return oldValue;
39 }
40 }
41 ++modCount;
42 if (++size > threshold)//步骤⑥
43 resize();
44 afterNodeInsertion(evict);
45 return null;
46 }
步骤：
- 当tab数组为空或长度为0时，执行resize()方法扩容，进入下一步
- 通过key计算hash值，得到数组索引，判断当该索引下的对象为空时，直接新建节点添加对象，跳到步骤⑥，否则进入步骤③
- 判断该数组索引下的首个元素key是否一样，相同则直接覆盖value，否则进入步骤④
- 判断该table[i]是否为treeNode，即是否为红黑树，如果是，直接插入键值对，不是则进入步骤⑤
- 遍历table[i]，判断该链表长度是否大于等于8（bigCount从0开始），如果是则把链表转换为红黑树，在红黑树中进行插入操作，如果不是，则进行链表的插入操作
- 判断实际容量是否大于threshold，是则扩容
扩容机制
jdk1.7中，进行扩容时，把旧数据放入到新数组中，链表的插入时，使用的是单链表的头插入方式，同一位置上的新元素总会被放到链头。在jdk1.8中，旧数组中一条链上的元素有可能被放到新数组的不同位置上
在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置。
JDK1.7和JDK1.8的HashMap性能比较
HashMap中，如果key经过Hash算法得出的数组索引位置全部不相同，即Hash算法非常好，则getKey()方法的时间复杂度为O(1)。如果Hash算法极差，所有元素都在一个链表下或红黑树下，则时间复杂度为O(N)和O(lgN)。jdk1.8的总体性能优于jdk1.7。