之前浅显地了解过HashMap是由数组加上链表实现的，但是一直没有真正理解到他的结构到底是怎样的，现在记录下自己学习HashMap的过程和理解，本篇研究了put与resize的源码实现、HashMap的关于桶大小及扩展的一些细节、以及jdk1.8做了哪些优化。

数组与链表的结合

在之前的学习中，了解到数组在内存中是一组连续的存储。它便于遍历和查询，但是不方便插入和删除。例如在一个存储了100个元素的ArrayList中，在索引为50的位置插入一个元素，则从索引为50开始往后的所有元素都需要后移，这无疑是非常大的消耗。但数组的查找时间复杂度小，为O(1)。而链表是一种离散的存储，插入和删除只需要修改链接的指向，但搜索的时间复杂度达到O(n)。
所以在HashMap中结合了两者的特性，让HashMap成为了一种寻址容易，插删也容易的数据结构。在这里用到的就是哈希表，哈希表为了解决冲突，主要有两种实现方法：开放地址法和链地址法。在HashMap中使用的是链地址法，也可称为拉链法，可理解为“链表的数组”。

HashMap中，有一个重要的Node[] table，Node实现了Map的静态内部类Entry，其中重要的属性有key，value，next，保存的就是键值对和到下一个Node的引用。

put与get的基本操作

1
2
3
4
5
6
7
8
//存储
int hash=key.hashCode();
int index=hash&(Entry[].length-1);
Entry[index]=value;
//取值
int hash=key.hashCode();
int index=hash&(Entry[].length-1);
return Entry[index];

这样，就基本将键值对均匀的分布在了数组中。
如果两个key经过hash后得到的index相同，会发生什么？例如Entry[0]=A之后，又来了一个元素B，其经过运算后的index也是0。这时就要用到链表的结构了，前面说道Entry有一个为next的属性，所以此时B.next=A，Entry[0]=B。Entry[0]处将一直存储着最后插入的元素。

代码详细剖析

jdk1.8，put->putVal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab;    //HashMap的元素数组
    Node<K,V> p;        //数组中准备插入的索引位置的原始Node
   
    int n, i;           //n：元素数组的长度，i：准备插入的经过hash运算过后的索引值
    
    if ((tab = table) == null || (n = tab.length) == 0) //如果元素数组为null或长度为0，则resize
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)          //如果原索引处为空，新建一个Node
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; 
        K k;    //原始key
        
        //如果索引处有原始Node，且key值相同，赋给e
        if (p.hash == hash &&   
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p;

        //如果为TreeNode，直接插入红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        //遍历链表准备插入
        else {
            for (int binCount = 0; ; ++binCount) {
                //如果Node的next为空，插入next
                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;
                }
                //如果插入元素与next的key值相同，直接覆盖
                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
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.8的扩容代码好像有点复杂，包含红黑树，先分析一下jdk1.7的resize

1
2
3
4
5
6
7
8
9
10
11
12
13
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {  //如果元素超过了最大容量1<<20(2^30) 1048576
      threshold = Integer.MAX_VALUE;
      return;
    }
  
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

transfer()将原有Entry数组的元素拷贝至新的容量更大的数组。拷贝后旧数组同一条Entry链上的元素可能将被放到不同位置上，因为元素的索引都经过了重新计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable) {
    Entry[] src = table;
   int newCapacity = newTable.length;
   for (int j = 0; j < src.length; j++) {
      Entry<K,V> e = src[j];
      if (e != null) {
        src[j] = null;//释放原数组索引位置对象，等待回收
        do {
           Entry<K,V> next = e.next;
           int i = indexFor(e.hash, newCapacity); //重新计算索引
           e.next = newTable[i]; //头插入，新元素.next指向原第一位元素(第一次指向null)
           newTable[i] = e;      //将最新的元素放在数组第一位
           e = next;             //遍历后移
           } while (e != null);
       }
   }
}

容量与负载因子

在HashMap中，有两个重要的值，它们是桶容量和负载因子：

1
2
3
4
5
6
7
8
9
/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的初始容量是16、负载因子是0.75。HashMap当前能存放的最大数据量threshold=(容量*负载因子)，超过这个数据量就要进行扩容，扩容后是之前容量的2倍。默认的0.75负载因子是一个对时间和空间的均衡，一般的情况下都不需要修改，如果场景比较特殊，比如内存很多而对时间效率要求高就可以降低负载因子的值；而如果内存紧张对时间效率要求也不高的话就可以增加负载因子的值，这个值可以超过1。

2次方桶的作用

在HashMap中，哈希桶的大小必须是2的N次方（一定是合数）。一般情况下，素数导致冲突的概率要小于合数，HashTable初始化桶的大小为11就是素数的应用。HashMap这样设计是为了在hash取模和扩容的时候做优化。接下来看下HashMap的hash算法和扩容机制，下面是hash算法与优化的取模运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
//HashMap在put值的时候，将先执行一遍hash算法，计算hash
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//hash算法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//取模，1.8没有这个方法，取模运算放在了具体调用的地方
static int indexFor(int h, int length) {
    return h & (length-1);
}

在平均一批元素的时候，我们常常的操作就是直接对容器的容量大小进行取模运算，这样元素的分布式相对比较均匀的。但是在计算机中模运算的消耗是比较大的，当桶的大小是2的n次方时，总有h%length = h&(length-1)。这个取模运算的效率是非常重要的，因为在put和get时，对元素的索引进行计算的时候都要经过这个方法，而&比%有更高的效率。

hash算法越分散均匀，hash碰撞的概率就越小，map的存取效率就越高。

1.8之后，使用的是2次幂的扩展，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。所以，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

参考：
美团点评技术团队：Java8系列之重新认识HashMap
猴子007：HashMap实现原理
沧海一滴：深入理解HashMap
jdk1.7, jdk1.8 源码

last update: 2018-06-27