文章目录

1. HashMap 存储结构
- - 1.1 HashMap底层结构
  - 1.2 HashMap 为什么采用数组 + 链表
  - - - Reference: 解决hash冲突的四种方法：
  - 1.2 HashMap 数组结构可否被替代
  - 1.3 HashMap 为何不直接使用红黑树
  - 1.4 HashMap 红黑树什么时候退化为链表
2. HashMap 存取过程
- - 2.1 HashMap put()方法
  - 2.2 HashMap get()方法
3. HashMap 容量相关
- - 3.1 HashMap 初始化容量
  - 3.2 HashMap 扩容为什么是2的次幂
  - 3.3 HashMap 扩容机制
4. HashMap 使用指南
- - 4.1 使用不可变类作为HashMap的Key
  - 4.2 实现自定义类作为HashMap的Key
  - - 4.2.1 重写 hashcode 和 equals 方法
    - 4.2.2 如何设计一个不变类

1. HashMap 存储结构

1.1 HashMap底层结构

JDK 1.8 的 HashMap 底层数据结构与 JDK1.7 时大致相同，主要为数组+链表。它采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。但在1.8 版本中如果链表元素数量达到 8 ，就会尝试进行树化操作（如果数组长度小于 64，则进行扩容操作，而不是树化操作），将链表转化为红黑树结构。故 HashMap 数据结构可作如下总结：

JDK 1.7：数组+链表
JDK 1.8：数组+链表+红黑树

static final int MIN_TREEIFY_CAPACITY = 64;

final void treeifyBin(Node<K,V>[] tab, int hash) {
  
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize(); // 如果数组长度小于 64， 则进行扩容操作，而不是树化操作
        else if ((e = tab[index = (n - 1) & hash]) != null) {
  
            TreeNode<K,V> hd = null, tl = null;
            do {
  
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
  
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

1.2 HashMap 为什么采用数组 + 链表

数组结构简单，利用元素 key的hash值对数组长度取模可以快速定位到数组下标 index，效率极高
链表是用来解决hash冲突问题，当出现 hashCode 值一样的情形，就在数组相应下标位置形成一条链表。这是解决hash冲突的链地址法

Reference: 解决hash冲突的四种方法：

链地址法
基本思想是将所有哈希地址为 i 的元素构成一个单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在链表中进行。链地址法适用于经常进行插入和删除情况。
开放定址法
也称再散列法，基本思想是当关键字key的哈希地址p=H（key）出现冲突时，以p为基础产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
再哈希法
同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key），直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
公共溢出区域法
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

1.2 HashMap 数组结构可否被替代

能否用LinkedList 代替

答案是可以，但是用数组效率最高。在HashMap中定位数组下标利用元素的key的哈希值对数组长度取模就可以，显然数组的查找效率比LinkedList高。

ArrayList底层是数组查找也快，能否用ArrayList

采用基本数组结构扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。而ArrayList的扩容机制是1.5倍扩容，默认容量为10，不利于高效定位。
```
private void grow(int minCapacity) {
    
     // overflow-conscious code
     int oldCapacity = elementData.length;
     int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍扩容，默认为10
     ......
 }
```

1.3 HashMap 为何不直接使用红黑树

当元素小于8个时，做查询操作链表结构已经能保证查询性能。
当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，这些都是性能损耗。

因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑是浪费性能。

1.4 HashMap 红黑树什么时候退化为链表

从源码看，节点数量为6的时候退转为链表,中间有个差值7可以防止链表和树之间频繁的转换。如果设计成链表个数超过8则链表转换成树结构，小于8则树结构转换成链表，如果一个HashMap不停插入删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率很低。

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  
           ......
            if (loHead != null) {
  
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map); // 解除树化
             ......
        }

2. HashMap 存取过程

2.1 HashMap put()方法

存储元素的过程如下：

对key 做hash() 运算，获取其hashCode 值, 可看到有对 key==null 返回 0 的处理，这就是HashMap允许 null 键的原因。另外 hash() 中将 hashCode 与 hashCode 无符号右移16位的值进行异或处理，是出于减少哈希冲突的目的，因为这个操作把原 hashCode 中没有使用到的高位数据也利用起来参与到运算中了。

Hash函数是指把一个大范围映射到一个小范围，目的是节省空间，使得数据容易保存。比较出名的有MurmurHash、MD4、MD5等等。

 static final int hash(Object key) {
  
        int h;
        // 此处 h与其低16位 异或 操作，目的是减少index定位时的 hash碰撞
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

懒加载策略，如果当前 Entry[] 数组尚未初始化，则调用 resize（）方法初始化。
使用 hash（）运算后的值与【数组长度-1】与运算后定位到数组 index，如果该位置上没有元素则插入。
如果碰撞了，【1】首先通过 equals（）比较 key，如相同则使用新的 value 覆盖旧 value，从此可知HashMap 只允许一个Key为null的键值对；【2】不符合前一条则首先判断碰撞的元素是否是树节点，即该位置链表是否已经转化成红黑树，如是则将新元素转化为树节点插入；【3】不符合前两条，遍历该数组位置链表，判断链表长度是否大于8，大于8则将链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作，遍历过程中若发现key已经存在直接覆盖value即可。
插入成功后，判断数组实际存在的键值对数量size是否超过了最大容量threshold，如果超过则进行扩容。

public V put(K key, V value) {
  
        return putVal(hash(key), key, value, false, true); // 
    }
    
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;
 }

2.2 HashMap get()方法

获取value的过程也很简单：

对key 做hash() 运算,获取用于定位数组下标的值。
使用 hash（）运算后的值与【数组长度-1】与运算后定位到数组下标index，取该位置上第一个节点 first，如其直接命中则直接返回。
如果有冲突，则通过key.equals(k)去查找对应的Entry：若为树，则在树中通过key.equals(k)查找，O(logn)；如果是链表，则在链表中通过key.equals(k)查找，O(n)。

public V get(Object key) {
  
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
  
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
  
            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;
    }

3. HashMap 容量相关

3.1 HashMap 初始化容量

HashMap默认容量为 16，最大容量为 1<<30 。扩容负载因子为 0.75，也就是默认容量下数组中实际存储的元素数量达到 16 * 0.75 = 12，就会触发扩容。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

一般建议使用 HashMap 的时候指定初始容量大小，因为随着元素的不断增加，如果实际容量与初始容量相差太大，HashMap会发生多次扩容，而其扩容机制决定了每次扩容都需要重建hash表，非常影响性能。

另外即便通过 HashMap(int initialCapacity) 设置初始容量的时候，HashMap也不一定会直接采用传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。从以下代码看，经过无符号右移和按位或运算, HashMap的容量最终会被设置成大于传入参数的最小的2的次幂（7–>8, 10–>16）。

  static final int tableSizeFor(int cap) {
  
        int n = cap - 1; // 参数值 -1 是为了处理传入参数值恰好是 2 的次幂的情况
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

3.2 HashMap 扩容为什么是2的次幂

HashMap为了存取高效就要尽量减少碰撞，也就是尽量把数据分配均匀，每个index下标上的链表(也可能是红黑树)长度需要大致相同, 这个算法实际就是取模，hash%length。

但是取模运算不如位移运算快。因此源码中优化为 hash()&(length-1),也就是hash%length 等价于 hash()&(length-1).

public V get(Object key) {
  
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
  
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
   // 注意，此处即为取模定位 index
       ......
    }

之所以取数组长度为 2 的n 次方,是因为2的n次方用二进制表示实际就是1后面n个0，而2的n次方-1，实际就是n个1。

例如长度为8时候，3&(8-1)–>(11 & 111)=3, 2&(8-1)–>(10 & 111)=2 ，下标不同，不碰撞。
而长度为5的时候，3&(5-1)=0, 2&(5-1)=0，都在0上，出现碰撞了。

所以，保证容积是2的n次方，是为了保证在做 hash&(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算, 尽量减少哈希冲突.

3.3 HashMap 扩容机制

HashMap 扩容为原来2倍，所以链表中节点的位置要么是在数组原位置，要么是在数组原位置再移动2次幂的数组位置，且链表元素的顺序不变。

JDK1.7中 HashMap旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置。1.8的优化解决了 1.7 版本 HashMap多线程扩容出现链表中两个节点 next 指针互相指向对方的死循环（HashMap Infinite Loop）问题。

以下代码中已经添加了注释，JDK1.8中HashMap 不需要像JDK1.7的实现那样重新计算hash值，而是复用原 hash 值，将其与原容量进行与操作，进而确定其数组下标是否需要改变。

例如原容量 oldCap = 16，二进制表示为： 00001 0000
则 key1=0001 1001, key2 = 0000 1001, 扩容前两个 key&(oldCap-1) 都在下标 9 位置
扩容时 key1&oldCap = 0001 0000=16 下标变化, key2&oldCap=0 下标不变

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;
         }
         // 没超过最大值，扩充为原来的2倍
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             newThr = oldThr << 1; // double threshold
     }
    ......
     threshold = newThr;
     @SuppressWarnings({
  "rawtypes"，"unchecked"})
         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = newTab;
     if (oldTab != null) {
  
         // 把每个bucket都移动到新的buckets中
         for (int j = 0; j < oldCap; ++j) {
  
             Node<K,V> e;
             if ((e = oldTab[j]) != null) {
  
                ......
                 else {
   // 重点，重新处理链表节点位置代码块
                     Node<K,V> loHead = null, loTail = null;
                     Node<K,V> hiHead = null, hiTail = null;
                     Node<K,V> next;
                     do {
  
                         next = e.next;
                         // 复用原 hash 值与 原容量与操作，若原容量为oldCap = 16 = 00001 0000
                           // 则 key1=0001 1001, key2 = 0000 1001, 扩容前两个[key&(oldCap-1)]都
                           // 在下标 9 位置
                           // 扩容时 key1&oldCap = 0001 0000=16 下标变化, key2&oldCap=0 下标不变
                         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);
                     // 放到new bucket里 位置与原索引相同
                     if (loTail != null) {
  
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     // 放到new bucket里，下标位置为 原索引 + oldCap 
                     if (hiTail != null) {
  
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
 }

4. HashMap 使用指南

4.1 使用不可变类作为HashMap的Key

一般用Integer、String这种不可变类当HashMap当key，最常用String。

因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。
HashMap 存取值的时候要用到 equals()和 hashCode()方法，键对象正确地重写这两个方法是非常重要的，通常不可变类已经很规范的覆写了hashCode()以及equals()方法。

使用可变类（如List）作为 HashMap 的key 的问题

例如把List 作为键，那么当这个 List 对象添加删除元素的时候 hashcode可能发生改变，这样可能会导致其在HashMap中数组 index下标定位不准，也就无法取出存储的value。

4.2 实现自定义类作为HashMap的Key

主要涉及两个关键点：

重写 hashcode 和 equals 方法
设计一个不变类

4.2.1 重写 hashcode 和 equals 方法

需要遵守以下四个原则：

两个对象相等，hashcode一定相等
两个对象不等，hashcode不一定不等
hashcode相等，两个对象不一定相等
hashcode不等，两个对象一定不等

4.2.2 如何设计一个不变类

类添加final修饰符，保证类不被继承
如果类可被继承就会破坏类的不可变性机制，只要子类覆盖父类的方法（如equals 和 hashCode）并且子类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。
所有成员变量必须私有，并且加上final修饰
通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为对象成员变量有可能在外部改变其值，所以第5点弥补这个不足。
不提供改变成员变量的方法，包括setter
避免通过其他接口改变成员变量的值，破坏不可变特性。
在getter方法中，不要直接返回对象本身，而是克隆对象并返回对象的拷贝
这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。
通过构造器初始化所有成员，进行深拷贝(deep copy)
如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改达到改变内部变量的效果。例如：

public final class Table {
    
    private final int[] myArray;  
    public Table (int[] array) {
    
        this.myArray = array; // myArray和array指向同一块内存地址
                           //修改传入的array对象的值可改变myArray内部的值
    }  
}

为了保证内部的值不被修改，可采用深度copy来创建一个新内存保存传入的值。正确做法：

public final class Table {
    
    private final int[] myArray;  
    public Table (int[] array) {
    
        this.myArray = array.clone();   
    }   
}

Java 8 HashMap 详解