HashMap源码解析

首先了解一下常见集合类底层数据结构：

• ArrayList -> 数组
  

• LinkedList -> 链表
  

• TreeMap
  

• HashMap -> 数组 + 链表（jdk 1.8之后，链表达到一定长度会转化为红黑树）
  

HashMap存储原理

HashMap存储的是key - value键值对类型的数据，通过对Key做hash，从而直接拿到数组下标，达到理论上存取的时间复杂度为O(1)。

对key的hash算法为：

对key进行hash运算，得到一个Int值，如果这个Int值大于HashMap中数组长度，则对长度进行取模，流程图（假设数组长度为1000）：

Hash碰撞：

如果添加元素时，发现对应下标已经有值了，则将该元素放到数组对应链表中（HashMap底层时数组 + 链表）

HashMap中数组初始大小

初始化HashMap，最终通过HashMap的双参数构造方法，无参构造最终也会通过双参数构造方法来初始化，只不过会传入一个默认值：

jdk 1.6：初始容积为16，装载因子0.75

首先两个老生常谈的变量：

• threshold：初始容积，看一下源码当中你的解释：

  The next size value at which to resize (capacity * load factor).

• loadFactor：负载因子，至于为什么是0.75呢

  先来说说为什么不是0.5或1，首先如果是0.5，那么每次容量达到一半就会扩容，初始容量是16，达到8时会扩容到32，16会扩容到64，造成空间利用率低下，而且扩容损耗性能，频繁扩容也让HashMap存储效率低；如果是1，那么每次容量用完才扩容，加大碰撞几率，导致链表中存储数据量变多，存取效率变低。

  再来看看官方解释（SDK 1.7）：

  默认负载因子（0.75）在时间和空间成本上提供了很好的折衷，较高的值会降低空间开销，但会提高查找成本；设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

  JDK 1.8：

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

  了解具体点可以参考松柏分布和指数分布

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

  其他参考：https://www.jianshu.com/p/f1142c24ccf3

下面看一下源码：

构造方法

• 构造方法 HashMap()：

  public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);
      this.loadFactor = loadFactor;
      this.threshold = tableSizeFor(initialCapacity);
  }
  

  参数：数组大小，装载因子（满载率）

  1. 校验传入数组大小范围 0 <= initialCapacity < (1 << 30) 10亿多
  2. 校验传入满载率范围 0 >= loadFactor 并且是个数字不是null

  这里并没有将数组创建出来（空数组），只是确定了数组长度

Entry类型

HashMap中数组存储的类型是Entry（jdk 1.7中），那么来看一下Entry源码：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    //...
}

可以看到，Entry成员变量只有四个，分别是hash key value next，所以实际上HashMap中数组（也就是源码中的table）存储模型就如下图所示：

存数据 put方法

问题：

1. 调用HashMap无参构造实例化，数组的初始容积和满载率各是多少？
2. 满载率可以修改吗，通过什么方式？
3. 为什么HashMap中数组的长度需要是2的整数次幂？
4. HashMap中数组是何时初始化的？
5. HashMap存储的键值对可以为null吗？
6. 什么是二次哈希/扰动函数，目的是什么？
7. HashMap在put时，是如何判断是否需要覆盖旧值的？（B站）
8. 新增元素时，如果数组上已有元素（冲突），那么新元素是如何插入的？
9. 什么是fail-fast？属性modCount有什么用？
10. HashMap如何判断是否扩容，扩容策略是什么？
11. 为什么HashMap中数组的长度需要是2的整数次幂？

大致流程：

• 存数据put()：

  public V put(K key,V value){
  	if (table == EMPTY_TABLE){
  		inflateTable(threshold);	//初始化数组 table
  	}
  	if(key == null){
  		return putForNullKey(value);	//key可存null，并且一定在数组第0位置的链表上
  	}
  	int hash = hash(key);  //通过位运算得到hash值
  	int i = indexFor(hash,table.length);
    // 判断key是否相等，是否执行覆盖操作
  	for(Entry<K,V> e = table[i]; e != null; e = e.next) {
  		Object k;
  		if (e.hash == hash && ((k = e.key) || key.equals(k))) { 
  			V oldValue = e.value;
  			e.value = value;
  			e.recordAccess(this);	//是给子类LinkedHashMap扩展用的
  			return oldValue;
  		}
  	}
    
    modCount++;
    addEntry(hash, key, value, i);
    return null;
  }
  

  1. 判断数组table是否为空，如果为空则调用inflateTable()方法来初始化数组

  2. 判断key是否是null，如果是则调用putForNullKey(value)来存key为null的情况。

  3. 通过hash()方法来获取hash值，这里获取的是二次哈希/扰动函数的值。

  4. 判断是否需要覆盖旧值，key相等条件是：key的hash是否相等；key的存储地址是否相等；key的值是否相等。若相等则覆盖并返回旧值。

  5. 没找到旧值，则调用addEntry()来添加新的节点。

• 数组初始化方法：inflateTable(int toSize)

  参数：toSize，也就是HashMap构造方法中确定的数组大小

• 找到大于等于传入参数的2的整数次幂数的方法：roundUpToPowerOf2()

  public static int roundUpTOPowerOf2(int number){
  	return number >= MAXIMUM_CAPACITY
  					? MAXIMUM_CAPACITY
  					: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
  }
  

  其中Integer.highestOneBit()方法返回传入参数的二进制的最高位，简化位运算流程如下：

  15 --> 0000 1111 --> 0000 1000 --> 8

  16 --> 0001 0000 --> 0001 0000 --> 16

  17 --> 0001 0001 --> 0001 0000 --> 16

  配合外层将参数做处理：(number - 1) << 1 ，从而达到找到传入参数向上的2的整数次幂的数。

• 成员变量：modCount，添加/删除时进行改变，在多线程同时操作HashMap，可以通过modCount提早发现异常，也是是有些人说的fail-fast

• 存放空key方法：putForNullKey(value)

  大致流程是取数组第1个元素（下标为0），遍历对应链表，如果找到key为null的，直接覆盖并返回旧值；否则新建数据并插入到链表中，返回null。

• 哈希算法：hash()

  final int hash(Object k) {
  	int h = hashSeed;		//JVM虚拟机启动时设置，如果没有设置则为0
    if (0 != h && k instanceof String) {
      return sun.misc.Hashing.stringHash32((String)k);
    }
    h ^= k.hashCode(); //h 或等 key的hashCode，由于h是0，所以这时 h = h.hashCode
    // 下面进行二次哈希或叫扰动函数，目的是让Hash值更加分散，不容易产生碰撞
    h ^= (h >>> 20) ^ (h >>> 12);	
    return h ^ (h >>> 7) ^ (h >>> 4);
  }
  

  返回二次哈希后的hash值。

• 高效的取模方法：indexFor()

  static int indexFor(int hash,int length){
  	return hash & length - 1;
  }
  

  通过巧妙的位运算取模，位运算如：

  hash: 0101 0101 0100 0011 （152179）

  length: 0000 0000 0000 1111 （15）

  result: 0000 0000 0000 0011 （3）

  前面的0都会被丢弃，只需关注length部分。

这里也解释了前面为什么length要是2的整数次幂，为的就是length - 1后能得到后面为 1111 的数据，

从而可以高效对一个很大的数字分配到较小下标上。

• 增加节点方法：addEntry()

  //参数：bucket是桶的意思，所以也有人把HasnMap中数组的每个格子称为一个桶🪣
  void addEntry(int hash, K key, V value, int bucketIndex) {
    //是否扩容
  	if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);	//真正创建节点
  }
  

  1. 判断是否进行扩容，条件：如果size超过阈值，并且创建节点的目标桶上有元素，也就是说即使数组大小超过阈值，只要目标桶上没有元素，就不需要进行扩容。
  2. 扩容策略：
  3. 调用createEntry()方法来真正增加节点。

• 真正增加节点方法：createEntry()

  void createEntry(int hash, K key, V value, int bucketIndex) {
  	Entry<K,V> e = table[bucketIndex];	// 原本数组上的元素
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
  }
  

  这里先获取了原本数组上的元素，然后把原本数组上的元素索引到新创建元素的next上，也就是将新元素放到数组上，原本的元素索引到到后面，也就是头插法（jdk 1.7），因为设计者认为最新插入的节点更容易被访问。

• 最后来总结一下put流程：

  1. 首先判断数组table是否创建，如果没创建则通过inflateTable方法，传入threshold容积来初始化数组（table）
     • 数组初始化：通过roundUpToPowerOf2方法找到大于threshold并且是2的整数次幂的数，与MAXIMUM_CAPACITY + 1取最小值作为table初始容积，然后初始化数组
  2. 判断key是否为null，如果为null则调用putForNullKey来存储key为null的情况（存储在数组第0个位置）
  3. 根据key调用hash方法获取hash值
  4. 通过indexFor（取模）传入hash值，获取要存储的桶（table）位置
  5. 判断是否有旧值，有则覆盖并返回
  6. 新建Entry（addEntry方法）：判断是否需要扩容（当前table存储的size大于等于容积threshold，并且存储的目标位置有元素）
  7. 扩容：
     • 重算新table大小（2倍length），创建新数组
     • 将旧数组table元素移动到新数组newTable（transfer）
     • 重新赋值threshold大小
     • 重算hash与桶位置（hash取模）
  8. 添加元素（createEntry）
     • 新建Entry
     • 赋值到table位置
     • size++

  如图：
  

取数据 get方法

• get方法：

  public V get(Object key) {
      if (key == null)
          return getForNullKey();
      Entry<K,V> entry = getEntry(key);
      return null == entry ? null : entry.getValue();
  }
  

  HashMap的get很简单，看代码就能懂了。

• getForNullKey()

  private V getForNullKey() {	//返回key为空情况，只存在table[0]对应链表中
      if (size == 0) {
          return null;
      }
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
          if (e.key == null)
              return e.value;
      }
      return null;
  }
  

• 根据key获取value方法getEntry()

  final Entry<K,V> getEntry(Object key) {
          if (size == 0) {
              return null;
          }
          int hash = (key == null) ? 0 : hash(key);
          for (Entry<K,V> e = table[indexFor(hash, table.length)];
               e != null;
               e = e.next) {
              Object k;
              if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k)))) //判断key相等
                  return e;
          }
          return null;
      }
  

jdk 1.7 Q&A：

1. 数据结构是怎样的？数组 + 链表

2. 怎么插入数据？头插法

3. 怎样解决hash冲突？预防：「二次哈希/扰动函数」 解决：「拉链法」

4. 默认容量是多少？「16」 即使传入15也会变成16

5. 数组何时创建？「第一次put」

6. HashMap中数组是何时初始化的？对应的链表是何时初始化的？

7. 碰撞时，如何确定已有元素与正在添加元素相同呢？

8. key，value可以传null吗？

去掉空布局距顶部间距；修复加载更多时可能切换布局类型；调整加载更多标题间距

调整Category菜单间距、字体颜色；价格和评分间距；

jdk 1.8与jdk1.7 HashMap区别

jdk 1.8的put()

第一次put()流程图：

public V put(K key, V value) {
    return this.putVal(hash(key), key, value, onlyifAbsent = false,evict = true);
}

putVal的onlyifAbsent参数是不在场证明含义，这里表示是否不覆盖旧值，默认put默认false，可以使用putIfAbsent()方法；evict则是给LinkedHashMap做扩展。

• 扩容时机

  1.7 先扩容 再添加

  1.8 先添加 在扩容

• 添加新元素方式

  1.7 头插法

  1.8 尾部添加

• 1.8 添加新元素，树化操作

• 1.8扩容后少进行一次hash运算

1.7 与1.8 区别Q&A：

1. 1.7 和 1.8 数据结构有什么不同？「在一定条件下会转化为红黑树」
2. 往链表插入数据的方式有什么不同？「1.7 头插法」 「1.8尾部插入」
3. 扩容后存储位置计算方式？「1.7 扩容后再进行哈希找索引」「1.8 对老的数组长度进行与运算，得出的值等于0则在低位，否则在高位」
4. 什么时候会把链表转化为红黑树？「列表长度大于8时」并且「数组大小大于64时（数组过小比如16，只会进行扩容）」