HashMap的学习笔记

1、HashMap简介

  1. HashMap的一个无序的Key-Value键值对数据结构
  2. 在JDK1.6和1.7中，HashMap采用位桶和链表实现，在JDK1.8中采用位桶+链表+红黑树实现
  3. HashMap的初始容量为16，且每次扩容均为2的次幂
  4. HashMap的负载因子为0.75
  5. HashMap的线程不安全的
  6. 当HashMap某一个桶中的链表个数大于8时(既阈值超过8)，链表自动转为红黑树

  7. HashMap底层为Node节点数组 

    1. Node(int hash, K key, V value, Node<K,V> next) {
    2. this.hash = hash;
    3. this.key = key;
    4. this.value = value;
    5. this.next = next;
    6. }

  8. HashMap是通过”拉链法”实现的哈希表。它包括几个重要的成员变量： table, size, threshold, loadFactor, modCount。
    ①table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
    ②size是HashMap的大小，它是HashMap保存的键值对的数量。
    ③threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=”容量*负载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
    ④loadFactor就是负载因子。
    ⑤modCount是用来实现fail-fast机制的。

2、HashMap的构造函数

HashMap提供了四种构造函数

①public HashMap(int initialCapacity, float loadFactor)

  1.  public HashMap(int initialCapacity, float loadFactor) {
  2.         if (initialCapacity < 0)
  3.             throw new IllegalArgumentException("Illegal initial capacity: " +
  4.                                                initialCapacity);
  5.         if (initialCapacity > MAXIMUM_CAPACITY)
  6.             initialCapacity = MAXIMUM_CAPACITY;
  7.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  8.             throw new IllegalArgumentException("Illegal load factor: " +
  9.                                                loadFactor);
  10.         this.loadFactor = loadFactor;
  11.         this.threshold = tableSizeFor(initialCapacity);
  12.     }

可以指定初始容量和负载因子的构造函数

②public HashMap

  1. public HashMap(int initialCapacity) {
  2.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  3. }

指定初始化容量，和使用默认的负载因子0.75,this调用的是①中的构造函数

③public HashMap()

  1. public HashMap() {
  2.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  3. }

使用默认容量和默认的负载因子

④public HashMap(Map<? extends K, ? extends V> m

  1. public HashMap(Map<? extends K, ? extends V> m) {
  2.     this.loadFactor = DEFAULT_LOAD_FACTOR;
  3.     putMapEntries(m, false);
  4. }

包含子Map的构造函数

3、HashMap的原理

HashMap采用的是链地址法（拉链法）

HashMap的学习笔记 - 图1

首先初始的是一个大小为16的数组

我们这里有不同的数组要进行存储。如12,28,91,31,108

我们定义一个最简单的Hash运算 y = key % n (key代表需要存储的数，n代表数组的大小)

12 % 16 = 12，我们就把这个数据放置在数组位置12上

31 % 16 = 15，同上余15，那我们就防止在15上面

28 % 16 = 12, 这时我们发现余数和上面第一个是一样的，这时候就发生了Hash碰撞，但是这个没问题，因为HashMap是运行Hash碰撞的，而且HashMap的底层结构是单向链表，我们只需要把28链接在12后面即可

Tips

当一个位置的链表长度（如果数组12这条链表后面挂载超过8个数据，那么这条链表就会转换成红黑树）

当各个位置存在数据的数量大于容量负载因子时，HashMap便会产生扩容

4、拉链法的数据结构

  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;
  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.     }
  14.     public final int hashCode() {
  15.         return Objects.hashCode(key) ^ Objects.hashCode(value);
  16.     }
  18.     public final boolean equals(Object o) {
  19.         if (o == this)
  20.             return true;
  21.         if (o instanceof Map.Entry) {
  22.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  23.             if (Objects.equals(key, e.getKey()) &&
  24.                 Objects.equals(value, e.getValue()))
  25.                 return true;
  26.         }
  27.         return false;
  28.     }
  30.     ......
  31. }

在Node类中，我们可以发现只存在一个next节点，由此证明Node是单链结构，但是还需要注意的是

1、Node类重写了equals方法，这个方法就是用来判断当Hash值一样时，如何判断是否是我们所想要取得的那个值

判断流程

①判断两者地址是否相同，相同则为所寻找的值

②判断目标对象类型是不是Map.Entry，如果是判断两者的key是否相等，再判断Vaule是否相等，都想得则为寻找的值，两者有其中之一不满足则返回false

2、Hashcode方法则就是同时对Key和Value进行hash操作，然后取异或（^）相同取0，不同取1

5、HashMap的初始化声明

1、DEFAULT_INITIAL_CAPACITY

  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

声明默认容量 << 是位运算符，1 << 4代表将二进制数1左移4位

1的二进制为1,左移4位为1000,再转换为十进制为16

2、MAXIMUM_CAPACITY

  1. static final int MAXIMUM_CAPACITY = 1 << 30;

声明最大容量为2的30次方

3、DEFAULT_LOAD_FACTOR

  1. static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的负载因子0.75,初始的默认容量为16，既160.75 = 12 ，在数组中有*超过12个位置有数据时，HashMap既需要扩容，那么为什么负载因子设定为0.75而不设定为1呢？

到这里就不得不介绍一下HashMap最基本的原理Hash操作

Hash，一般翻译做“散列”，也有直接音译为“哈希”的。那么哈希函数的是什么样的？大概就是 value = hash(key)，我们希望key和value之间是唯一的映射关系。

因为Hash算法的问题，是存在两个不同的key经过Hash算法后获得相同的Hash的值的

因为HashMap是拉链法，所有相同的Hash值的数据会挂载在数组的同一个位置

HashMap的学习笔记 - 图2

在这里12,28,108,140都是相同的hash值（y = key % n ）

当不断出现hash值为12的数，就会不断的挂载在12上面，会导致这条链表越来越长，当超过8个时会转换成红黑树，但是虽然转换为红黑树，但是其存储结构任然为链表

链表我们知道有一个特性，删除和添加操作时间复杂度都非常低，但是对于查找来说，会花费很多的时间

因为链表需要从第一个不断的查找到所需要的那个值，无法进行快速的访问

所以减小Hash的碰撞，既在上面这个例子中，我能减少12这个hash值出现的频率，那么我们12这个位置挂载的数据不就会减少了吗？链表的长度缩短，链表的查找时间就会大大提升

既然我们已经明白了只要能减小碰撞，那么就可以使HashMap保持在一个比较快速的情况下

那么现在我们举个例子

情况1：负载因子为0.75，存储1到16，16个数

情况2：负载因子为0.25，存储1到16，16个数

情况3：负载因子为1.00，存储1到16，16个数

HashMap容量为16，假设花费空间为16b

①情况1，16 * 0.75 = 12 ，在存储前12个数时，分布在12个地方，在存储第13个数时，HashMap的容量开始扩容，变为32个，前12个已经存储过的数字位置不变，剩余4个可能会随机分布在剩下的（32-12）20个位置，此时花费空间为32b

总结：花费空间位32，4个数据分布在20个位置，Hash碰撞概率较低

②情况2，16 * 0.25 = 4，在存储钱4个数时，分布在4个地方，在存储第4到8个数时，HashMap开始扩容，容量变为32，4个数据可能分布在(32 - 4) 28个位置，在存储第8到12个数时，HashMap开始扩容，容量变为64，4个数据可能分布在(64 - 8) 56个位置，在存储第12到16个数时，HashMap开始扩容，容量变为128，4个数据可能分布在(128 - 12) 112个位置，空间花费128b

总结：空间花费128b，数据分布较广，Hash碰撞概率极低，但是空间花费很大

③情况3,16 * 1 = 16 ，存储前12个数据时，分布在12个位置，在存储13-16四个数据时，因为没有扩容，位置还是4个，所以4个数据分布在4个位置，碰撞概率较高

总结：空间花费16b，数据集中，碰撞概率大

所以总的来说，如果负载因子很大的话，链表会很长，查询会很费时间，如果很小的话，又会造成空间的大量浪费

0.75是一个在空间和时间上面折中的考虑

JDK1.8HashMap源码中也有介绍

  1. * Because TreeNodes are about twice the size of regular nodes, we
  2. * use them only when bins contain enough nodes to warrant use
  3. * (see TREEIFY_THRESHOLD). And when they become too small (due to
  4. * removal or resizing) they are converted back to plain bins.  In
  5. * usages with well-distributed user hashCodes, tree bins are
  6. * rarely used.  Ideally, under random hashCodes, the frequency of
  7. * nodes in bins follows a Poisson distribution
  8. * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
  9. * parameter of about 0.5 on average for the default resizing
  10. * threshold of 0.75, although with a large variance because of
  11. * resizing granularity. Ignoring variance, the expected
  12. * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
  13. * factorial(k)). The first values are:
  14. *
  15. * 0:    0.60653066
  16. * 1:    0.30326533
  17. * 2:    0.07581633
  18. * 3:    0.01263606
  19. * 4:    0.00157952
  20. * 5:    0.00015795
  21. * 6:    0.00001316
  22. * 7:    0.00000094
  23. * 8:    0.00000006
  24. * more: less than 1 in ten million

翻译过来就是

理想状态下，在随机哈希值的情况，对于loadfactor = 0.75 ，虽然由于粒度调整会产生较大的方差，桶中的Node的分布频率服从参数为0.5的泊松分布。

stackoverflow一个回答为

一个bucket空和非空的概率为0.5，通过牛顿二项式等数学计算，得到这个loadfactor的值为log（2），约等于0.693. 同回答者所说，可能小于0.75 大于等于log（2）的factor都能提供更好的性能，0.75这个数说不定是 pulled out of a hat。

4、TREEIFY_THRESHOLD

  1. static final int TREEIFY_THRESHOLD = 8;

我翻译过来是树化阈值

也就是说当链表的长度超过8时，会转换成红黑树

5、UNTREEIFY_THRESHOLD

  1. static final int UNTREEIFY_THRESHOLD = 6;

当执行resize操作时，当桶中bin的数量少于UNTREEIFY_THRESHOLD时使用链表来代替树。默认值是6

6、MIN_TREEIFY_CAPACITY

  1. static final int MIN_TREEIFY_CAPACITY = 64;

当桶中的bin被树化时最小的hash表容量。（如果没有达到这个阈值，即hash表容量小于MIN_TREEIFY_CAPACITY，当桶中bin的数量太多时会执行resize扩容操作）这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。

7、table

  1. transient Node<K,V>[] table;

HashMap中初始化的数组

8、size

  1. transient int size;

size为HashMap中存储数据的数量

9、modCount

  1. transient int modCount;

modCount是Fail-Fast判断的一个重要方式Fial-Fast机制详解

10、entrySet

  1. transient Set<Map.Entry<K,V>> entrySet;

返回全部的Map集合

6、HashMap经典方法解释

1、Get方法

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

我们发现在get方法中，并不是直接通过get方法获取到这个Map，是调用了getNode这个方法

那我们便来看看getNode方法是干什么的

  1. final Node<K,V> getNode(int hash, Object key) {
  2.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  3.     if ((tab = table) != null && (n = tab.length) > 0 &&
  4.         (first = tab[(n - 1) & hash]) != null) {
  5.         if (first.hash == hash && // always check first node
  6.             ((k = first.key) == key || (key != null && key.equals(k))))
  7.             return first;
  8.         if ((e = first.next) != null) {
  9.             if (first instanceof TreeNode)
  10.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  11.             do {
  12.                 if (e.hash == hash &&
  13.                     ((k = e.key) == key || (key != null && key.equals(k))))
  14.                     return e;
  15.             } while ((e = e.next) != null);
  16.         }
  17.     }
  18.     return null;
  19. }

方法乍一看很复杂，我们便一层一层来看

①首先，我们来看看声明情况

  1. Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

声明并没有什么复杂的，声明了一个数组tab和一个节点first，e，还有一些int型变量

②第一层if

  1. if ((tab = table) != null && (n = tab.length) > 0 &&
  2.     (first = tab[(n - 1) & hash]) != null) {

首先映入眼帘的是这个table其次呢是这个tab[(n - 1) & hash])

这个table其实是Hashmap的初始化数组，上来便把这个数组赋值给tab，然后判断是否为空，而且判断length是否大于0

但是呢，这里面的重点是tab[(n - 1) & hash])是什么意思

tab我们已经知道了，是HashMap里面初始化的数组，它的每一个下标都代表着一条单链

我们假设访问tab[1]，如果tab[1]上面有数据的话，我们就能访问到这条单链，通过遍历这个单链，我们就能寻找到这条单链上的全部数据

那么为什么 (n - 1) & hash 能代替数组下表呢

首先，我们先举几个例子

9 % 4 = 1 ， 21 % 16 = 5

12的二进制为1001,3的二进制为0011，两者进行于操作（只有两者都为1，才为1） 得到的是0001 既1

21的二进制为10101,15的二进制位01111，两者也同样进行于操作,得到00101 既5

这时我们就会发现当一个数和2的次幂进行求余运算时，　当 lenth = 2n 时，X % length = X & (length - 1)

所以说，为什么HashMap的容量设计为2的次幂，因为于运算的速度大大快于求余运算，通过2的次幂的大小，我们可以快速的寻找到目标位置

那么get方法后面的代码我们也就能很容易的理解了

7、HashMap面试问题总结

1、你了解重新调整HashMap大小存在什么问题吗？

答：在多线程环境下，如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。