HashMap

HashMap采用Hash表存储数据，由数组+链表的结构生成。数组的位置由key的hashcode的方法生成，每个数组位置存储一个Entry对象。因为数组的位置是由hashcode通过特定的算法生成的，所以会发生hash冲突。

当发生hash冲突时，将会把新的元素对象通过链表的方式连接到目标数组元素的首部/尾部（jdk1.7采用头插法，jdk1.8采用尾插法），当链表的长度大于8时，链表将会转换为红黑树。

源码解析

主要的属性

使用hash表存储，容器是一个数组：

实际添加的元素数量由size属性记录：

数组的默认容量：

数组的最大容量：

当向数组中不断的添加元素时，超过threshold扩容边界，就会发生扩容：

而扩容边界是由扩容因子决定，threshold = 当前数组的容量 * loadFactor ：

默认的扩容因子值为 0.75，如果是一个16容量的数组，当用了12个容量位置时（16 * 0.75 = 12），就会触发扩容操作。

实际扩容时，将会按照二倍扩容的方式对数组进行扩容。

构造器

分别指定初始容量以及扩容因子，如果不传则使用默认值16以及0.75。

其中边界值threshold的大小生成是通过如下方法决定的，他始终会返回一个2^n的数：

put方法

其中，使用key计算目标的hash值（使用key的hashCode右移16位）：

然后调用putVal方法，其中，putVal方法的具体逻辑如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // 如果hash表（也就是数组table）为空，先初始化hash表
  // resize方法会对 table 成员变量进行初始化
  // 最后获取新的hash表的容量n
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  
  // 计算目标key在数组中的位置索引 i 变量， (n - 1) & hash，等效于 hash % length
  // 取出 i 位置的元素 p
  // 如果 p == null，说明没有发生hash冲突
  // 则创建一个Node对象，并放入到数组中
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  
  // 否则发生了hash冲突
  else {
    Node<K,V> e; K k;
    // 如果原位置的p，这个节点的key与新添加的key的值相同
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 如果原位置的p，这个节点类型是 TreeNode，说明p处在红黑树中，将目标元素放入到红黑树中
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 如果原位置的p，这个节点类型是链表
    else {
      // 从头至尾遍历链表
      // 如果遍历到尾部没有发现key相同的情况，就创建一个Node，将其添加到链表的最后（尾插法）
      //        插入完成后，判断当前链表的长度，如果当前链表的长度大于 TREEIFY_THRESHOLD - 1
      //        则触发链表转换红黑树的操作
      //        因为到达了链表结尾，所以e对象一定为null
      // 但如果这个过程中发现了目标key与当前key相同的情况
      //        结束循环，获取与之相同的这个节点e
      //        此时e一定不为null
      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;
      }
    }
    
    // 如果e不为空，就代表存在相同key的情况
    // 将这个对象的值替换为新的value，并返回旧的value
    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;
}

resize 数组的扩容

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;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            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);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

加载因子为什么是 0.75

如果扩容因子为1：只有到16位置都满了之后才会发生扩容。虽然这时候空间利用率极大，但是会很容易发生hash碰撞，特别是剩余的空间不多时，这时候查询效率就会越低。

如果扩容因子为0.5：这时碰撞的概率极低，所以产生链表的概率也低，查询效率极高，但是空间利用率极低。

0.75是对时间与空间的成本上的折中。

主数组的长度为什么必须为2的n次方？

确定目标key在数组的位置上是使用 (length - 1) & hash的方式产生的，等效于length % hash，而如果length的长度不是2的次幂，则这个等效就不会成立
为了防止hash冲突
image-20220303225229365

最后更新于2年前

这有帮助吗？