前文：HashMap是Java程序员最常用的映射（键值对）处理数据的容器。随着JDK版本的更新，1.8相较于1.7来说又引入了红黑树和扩容优化等底层优化内容。

1.部分容器的继承关系：

1.HashMap：基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并允许使用null值和null键，但是键值只能有一个为null。（除了非同步和允许使用 null 之外，HashMap类与Hashtable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

       此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get和put）提供稳定的性能。迭代 collection 视图所需的时间与HashMap实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

       HashMap的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

2.Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

3.LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

4.TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

5.WeakHashMap：若键映射，允许释放映射所指的对象，这是为了解决某类特殊问题而设计的。如果映射之外没有引用指向某个键，则键可以被垃圾回收器收集。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

---

2.HashMap底层实现原理：

    HashMap底层是由数组加链表或是红黑树的形式实现的。

先来看看HashMap中存的是什么：

   HashMap中存的是Node键值对，Node是HashMap中的一个内部类（HashTable中存的是Entry虽然名字不同但是属性方法基本一样），Node／Entry实现了Map.Entry接口其本质就是键值对。

    HashMap使用哈希表和数组来存储和维护数据，每个数组元素上都有一个链表。当Node需要被put进HashMap中时，首先会获得键值（Key）的HashCode（）方法返回值，再将返回值进行hash，得出数组下标。（注：有关HashCode（）和equals（）方法重写的内容可以看我的另一篇文章浅谈HashCode（）和equals（）。HashMap中的哈希方法下文中会详细讲解。）得出下标后仔进行链表的储存。

---

接下来我们就进入源码：

HashMap中的属性：

static final intDEFAULT_INITIAL_CAPACITY=1<<4;//默认初始长度为16

static final floatDEFAULT_LOAD_FACTOR=0.75f;//负载因子默认为0.75，一般不需要改变

transient int size;//HashMap中实际存储的键值对数量。

int threshold;//所能容纳的key-value对极限

      Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

      结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

        size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

        一般来说Hash类的容器中桶的数量是素数，如HashTable桶的初始化大小就是11。因为相对来说素数导致冲突的概率要小于合数。但是HashMap中桶的大小却是必须是2的n次方。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

---

功能实现：

1.确定哈希桶数组位置索引：不管是查找、增加还是删除，定位哈希桶的位置总是第一步，那么定位功能的实现就对HashMap的性能起了很大作用。

方法一：

static final int hash(Object key) {

int h;

return(key ==null) ?0: (h = key.hashCode()) ^ (h >>>16);

}

方法二：

static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的

return h & (length-1);  //第三步 取模运算

}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

方法二中，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

方法一是JDK1.8中的方法，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。（JDK1.8也会对最后结果取模运算只不过该过程在具体的put、get方法中完成）如图

2.put方法的实现：

put方法流程图

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

JDK1.8HashMap的put方法源码如下:

1 public V put(K key, V value) {

2     // 对key的hashCode()做hash

3     return putVal(hash(key), key, value, false, true);

4 }

5

6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

7                boolean evict) {

8     Node[] tab; Node p; int n, i;

9     // 步骤①：tab为空则创建

10     if ((tab = table) == null || (n = tab.length) == 0)

11         n = (tab = resize()).length;

12     // 步骤②：计算index，并对null做处理

13     if ((p = tab[i = (n - 1) & hash]) == null)

14         tab[i] = newNode(hash, key, value, null);

15     else {

16         Node e; K k;

17         // 步骤③：节点key存在，直接覆盖value

18         if (p.hash == hash &&

19             ((k = p.key) == key || (key != null && key.equals(k))))

20             e = p;

21         // 步骤④：判断该链为红黑树

22         else if (p instanceof TreeNode)

23             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

24         // 步骤⑤：该链为链表

25         else {

26             for (int binCount = 0; ; ++binCount) {

27                 if ((e = p.next) == null) {

28                     p.next = newNode(hash, key,value,null);

//链表长度大于8转换为红黑树进行处理

29                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

30                         treeifyBin(tab, hash);

31                     break;

32                 }

// key已经存在直接覆盖value

33                 if (e.hash == hash &&

34                     ((k = e.key) == key || (key != null && key.equals(k))))

35                            break;

36                 p = e;

37             }

38         }

39

40         if (e != null) { // existing mapping for key

41             V oldValue = e.value;

42             if (!onlyIfAbsent || oldValue == null)

43                 e.value = value;

44             afterNodeAccess(e);

45             return oldValue;

46         }

47     }

48     ++modCount;

49     // 步骤⑥：超过最大容量 就扩容

50     if (++size > threshold)

51         resize();

52     afterNodeInsertion(evict);

53     return null;

54 }

3.resize扩容机制：当原本的HashMap无法容纳更多的Node时就需要扩容

由于JDK1.8对该部分做了一些优化我们先研究JDK1.7的源码再来看看1.8的优化：

1 void resize(int newCapacity) {  //传入新的容量

2     Entry[] oldTable = table;    //引用扩容前的Entry数组

3     int oldCapacity = oldTable.length;

4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了

5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了

6         return;

7     }

8

9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组

10     transfer(newTable);                         //！！将数据转移到新的Entry数组里

11     table = newTable;                           //HashMap的table属性引用新的Entry数组

12     threshold = (int)(newCapacity * loadFactor);//修改阈值

13 }

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

1 void transfer(Entry[] newTable) {

2     Entry[] src = table;                   //src引用了旧的Entry数组

3     int newCapacity = newTable.length;

4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组

5         Entry e = src[j];             //取得旧Entry数组的每个元素

6         if (e != null) {

7             src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）

8             do {

9                 Entry next = e.next;

10                 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置

11                 e.next = newTable[i]; //标记[1]

12                 newTable[i] = e;      //将元素放在数组上

13                 e = next;             //访问下一个Entry链上的元素

14             } while (e != null);

15         }

16     }

17 }

上述方法的扩容理念大致就是当HashMap中的键值对数量超过阈值时进行扩容，把容量扩展为原来的2的n次方倍，取得原来HashMap中每个键值对并对每个键值对进行重新计算数组分配位置rehash。过程例子如下：

假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。

上述方法虽然比较完善但还存在不足，为每个Node重新计算下标是非常耗时的事情，JDK1.8就对此做了如下优化：

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”（原索引＋原来数组长度），可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。

JDK1.8源码：

1 final Node[] resize() {

2     Node[] oldTab = table;

3     int oldCap = (oldTab == null) ? 0 : oldTab.length;

4     int oldThr = threshold;

5     int newCap, newThr = 0;

6     if (oldCap > 0) {

7         // 超过最大值就不再扩充了，就只好随你碰撞去吧

8         if (oldCap >= MAXIMUM_CAPACITY) {

9             threshold = Integer.MAX_VALUE;

10             return oldTab;

11         }

12         // 没超过最大值，就扩充为原来的2倍

13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

14                  oldCap >= DEFAULT_INITIAL_CAPACITY)

15             newThr = oldThr << 1; // double threshold

16     }

17     else if (oldThr > 0) // initial capacity was placed in threshold

18         newCap = oldThr;

19     else {               // zero initial threshold signifies using defaults

20         newCap = DEFAULT_INITIAL_CAPACITY;

21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

22     }

23     // 计算新的resize上限

24     if (newThr == 0) {

25

26         float ft = (float)newCap * loadFactor;

27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

28                   (int)ft : Integer.MAX_VALUE);

29     }

30     threshold = newThr;

31     @SuppressWarnings({"rawtypes"，"unchecked"})

32         Node[] newTab = (Node[])new Node[newCap];

33     table = newTab;

34     if (oldTab != null) {

35         // 把每个bucket都移动到新的buckets中

36         for (int j = 0; j < oldCap; ++j) {

37             Node e;

38             if ((e = oldTab[j]) != null) {

39                 oldTab[j] = null;

40                 if (e.next == null)

41                     newTab[e.hash & (newCap - 1)] = e;

42                 else if (e instanceof TreeNode)

43                     ((TreeNode)e).split(this, newTab, j, oldCap);

44                 else { // 链表优化重hash的代码块

45                     Node loHead = null, loTail = null;

46                     Node hiHead = null, hiTail = null;

47                     Node next;

48                     do {

49                         next = e.next;

50                         // 原索引

51                         if ((e.hash & oldCap) == 0) {

52                             if (loTail == null)

53                                 loHead = e;

54                             else

55                                 loTail.next = e;

56                             loTail = e;

57                         }

58                         // 原索引+oldCap

59                         else {

60                             if (hiTail == null)

61                                 hiHead = e;

62                             else

63                                 hiTail.next = e;

64                             hiTail = e;

65                         }

66                     } while ((e = next) != null);

67                     // 原索引放到bucket里

68                     if (loTail != null) {

69                         loTail.next = null;

70                         newTab[j] = loHead;

71                     }

72                     // 原索引+oldCap放到bucket里

73                     if (hiTail != null) {

74                         hiTail.next = null;

75                         newTab[j + oldCap] = hiHead;

76                     }

77                 }

78             }

79         }

80     }

81     return newTab;

82 }

另外HashMap是线程不安全的，尤其在多线程下进行resize扩容尤其容易形成环形链表。如果在多线程情况下推荐使用ConcurrentHashMap。