应该知道的HashMap源码分析

概括

HashMap是关联数组、哈希表和红黑树的集合。线程不安全。允许空键和空值。这是不正常的。

底层数据结构是一个数组，称为哈希表。每个位置都有一个链表。链表中的每个节点都是 HashMap 中的每个元素。

如果链表的元素个数大于等于8，则链表会转化为红黑树，以提高查询效率。

HashMap的结构如下：

下图是HashMap继承和实现的接口

基本数据结构

桶阵列

一个数组，每个位置后跟一个链表。

瞬态节点<K,V>[] 表；

链表节点

静止的
  class Node<K,V> 实现 Map.Entry<K,V> {
  最终的整数哈希；// 哈希值
  最终K键；
  V值；
  下一个节点<K,V>；// 链表中的下一个节点
// 构造函数
  Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = 哈希；
    this.key = 键；
    this.value = 值；
    this.next = 下一个；
  }
  public final K getKey() { 返回键；}
  公共最终 V getValue() { 返回值；}
  public final String toString() { return key + "=" + value; }
// 节点的hashCode是通过key和value的hashCode异或得到的。
  公共最终 int hashCode() {
    返回 Objects.hashCode(key) ^ Objects.hashCode(value);
  }
// 设置新值并返回旧值
  公共最终 V setValue(V newValue) {
    V oldValue = 值；
    值 = 新值；
    返回旧值；
  }
// 判断是否为节点。
  公共最终布尔等于（对象 o）{
    如果（o == 这个）
      返回真；
    if (o instanceof Map.Entry) {
      Map.Entry<?,?> e = (Map.Entry<?,?>)o;
      if (Objects.equals(key, e.getKey()) &&
          Objects.equals(value, e.getValue()))
        返回真；
    }
    返回假；
  }
}

红黑树

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  TreeNode<K,V> parent;  // Father node
  TreeNode<K,V> left;			// Left son
  TreeNode<K,V> right;		// Right son
  TreeNode<K,V> prev;    // needed to unlink next upon deletion
  boolean red; 					// colour
  TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
  }
// Return to root node
  final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
      if ((p = r.parent) == null)
        return r;
      r = p;
    }
  }
}

基本要素

在查看源代码之前，您需要了解一些常量的含义。只是有印象。

负载系数

总容量 * 负载系数 = 阈值

如果地图中的元素数量大于阈值，则需要对其进行扩展。

如果填充比例很大，则意味着使用了大量空间。如果不是一直进行扩展，链表会越来越长，所以搜索的效率很低，因为链表的长度很大(红黑后会提升很多)树在最新版本中使用)。扩展后，原链表数组的每个链表会被分成两个子链表，挂在新链表数组的hash位置，这样每个链表的长度减少，查找效率高增加

// 默认初始容量为 16。容量的大小必须是 2 的几个幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
// 最大容量不应超过 1 < 30 
static final int MAXIMUM_CAPACITY = 1 << 30; 
// 负载因子为 0.75 
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
// 树的阈值。单个链表中的元素数。链表向红黑树转换的判断条件。
静态最终 int TREEIFY_THRESHOLD = 8; 
// 树退化的阈值。单个链表中的元素数。红黑树退化的判断条件
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树容量。这是指地图中元素的总数。
静态最终 int MIN_TREEIFY_CAPACITY = 64; 
// ---------------------------------------------- 
//每个位置有几个元素的哈希表。
瞬态节点<K,V>[] 表；
瞬态集<Map.Entry<K,V>> entrySet; 
// 一个map中的元素个数
transient int size; 
// 修改次数
瞬态 int modCount; 
// 扩容阈值。如果超过阈值，将扩大容量。（容量 * 负载因子）
int 阈值；
// 哈希表的加载因子
final float loadFactor;

构造函数

有四种类型的构造函数。详情请参考以下代码注释。

// 给定初始容量，负载因子
public HashMap(int initialCapacity, float loadFactor) { 
  if (initialCapacity < 0) 
    throw new IllegalArgumentException("Illegal initial capacity: " +                                        initialCapacity); 
  如果（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); 
} 
// 给定初始容量
public HashMap(int initialCapacity) {
  // 调用上面的构造函数，给定容量和负载因子
  this(initialCapacity, DEFAULT_LOAD_FACTOR); 
} 
// 默认
public HashMap() { 
  this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他字段默认
} 
// 从现有地图创建一个新地图。
public HashMap(Map<? extends K, ? extends V> m) { 
  this.loadFactor = DEFAULT_LOAD_FACTOR; 
  putMapEntries(m, false); 
}

构造函数调用以下代码块。

// 返回大于或等于 cap 的最小值 2 的幂数。
静态最终 int tableSizeFor(int cap) { 
  int n = cap - 1; 
  // 即把二进制最高位1后的位置全部改为1 
  n |= n >>> 1; 
  n |= n >>> 2; 
  n |= n >>> 4; 
  n |= n >>> 8; 
  n |= n >>> 16; 
	// 与最大容量相比，不能超过最大容量。
  返回 (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ？最大容量：n + 1；
} 
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
  int s = m.size(); 
  if (s > 0) { 
    if (table == null) { // 预大小
      // 计算阈值的大小。
      float ft = ((float)s / loadFactor) + 1.0F; 
      // 与最大容量相比，如果超过最大容量，则成为最大容量。
      int t = ((ft < (float)MAXIMUM_CAPACITY) ? 
               (int)ft : MAXIMUM_CAPACITY); 
      if (t > threshold) 
        // 将阈值重新计算为 2 的幂。
        threshold = tableSizeFor(t); 
    } 
    else if (s > threshold) 
      // 如果现有集合元素个数大于阈值，则需要进行扩展。
      调整大小（）；
    // 遍历集合，一一加入当前集合。
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
      K key = e.getKey(); 
      V 值 = e.getValue(); 
      putVal(hash(key), key, value, false, evict); 
    } 
  } 
}

HashMap的访问和扩展

扩张

HashMap 的默认容量为 16，扩展时调整为原来的两倍。所以容量必须是 2 的某个幂。

final Node<K,V>[] resize() { 
  Node<K,V>[] oldTab = table; 
  // 获取地图的大小。
  int oldCap = (oldTab == null) ? 0 : oldTab.length; 
  // 当前阈值
  int oldThr = threshold; 
  int newCap，newThr = 0；
  // 当前容量大于0 
  if (oldCap > 0) { 
    // 当前容量已达到上限
    if (oldCap >= MAXIMUM_CAPACITY) { 
      // 阈值设置为2 ^ 31-1 
      threshold = Integer. MAX_VALUE; 
      // 返回当前哈希表，不扩展
      return oldTab; 
    }
    // 新容量扩大到旧容量的两倍，新容量小于最大容量，旧容量大于等于16 
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
             oldCap >= DEFAULT_INITIAL_CAPACITY) 
      newThr = oldThr << 1; // 阈值加倍
  } // 如果当前表为空但有阈值。表示初始化时指定了容量和阈值的情况
  else if (oldThr > 0) // 如果有旧阈值，则新容量等于旧阈值，旧阈值是2的几个幂
    newCap = oldThr; 
  else { // 默认情况下，如果没有容量或阈值，则设置默认容量和阈值
    newCap = DEFAULT_INITIAL_CAPACITY; 
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
  } 
  if (newThr == 0) { // 如果新阈值为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) { 
      // 临时节点 e 
      Node<K,V> e; 
      // 临时节点引用当前位置。
      if ((e = oldTab[j]) != null) { 
        // GC 
        oldTab[j] = null;将旧哈希表的位置设置为null; 
        // 如果当前位置只有一个元素，则将其插入到新表中，
        // e. Hash & (newcap - 1) 这是计算当前节点在哪里
        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 { // 保留顺序
          // 低序列表的头尾，0 ～ oldcap - 1 
          Node<K,V> loHead = null, loTail = null; 
          // 高阶链表的头尾 oldCap ～ newCap - 1 
          Node<K,V> hiHead = null, hiTail = null; 
          // 临时变量
          Node<K,V> next; 
          做 {
            下一个 = e.next;
            // 判断二进制的最高位是0还是1，如果是0，则将节点放入低位链表，否则为高位链表。
            if ((e.hash & oldCap) == 0) { 
              if (loTail == null) 
                loHead = e; 
              否则
                loTail.next = e; 
              loTail = e; 
            } // 二进制最高位为1，节点放入高阶链表
            else { 
              if (hiTail == null) 
                hiHead = e; 
              否则
                hiTail.next = e; 
              hiTail = e; 
            } 
          } while ((e = next) != null);
          // 下面的列表放在j的位置，
          if (loTail != null) { 
            loTail.next = null; 
            newTab[j] = loHead; 
          } 
          // 高阶列表放在j+oldCap的位置。
          if (hiTail != null) { 
            hiTail.next = null; 
            newTab[j + oldCap] = hiHead; 
          } 
        } 
      } 
    } 
  }
  返回 newTab; 
}

如果当前容量大于0且当前容量达到上限，则不扩容直接返回。没有达到上限，扩大到原来的两倍。

如果当前容量为0，则将容量和阈值设置为默认值。

对旧表中的元素进行分类，计算每个key的hash值，判断key是在(原位置)还是(原位置+旧容量)

放置值

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) { 
  // tab存储当前哈希表，p为临时变量。
  节点<K,V>[] 选项卡；节点<K,V> p; 国际n，我；
  // 如果哈希表为空，则应先对其进行扩展。
  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 { 
    // e 是一个临时变量。如果它不为空，则意味着该值应该像键一样被覆盖。
    节点<K,V> e; Ｋ；
    // hash相同，找到位置，key相同，覆盖。e 记录要覆盖的位置。
    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); 
          // 如果添加的节点数> = 8，则转化为红黑树。
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 表示第一个
            treeifyBin(tab, hash); 
          休息; 
        } 
        // 在遍历的过程中，key是一样的，tocover，e就是要覆盖的位置，直接break。
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k))))
          中断；
        p = e; 
      }
    } 
    // 有需要覆盖的位置。
    if (e != null) { // 键
      V 的现有映射oldValue = e.value; 
      if (!onlyIfAbsent || oldValue == null) 
        e.value = value; 
      afterNodeAccess(e); 
      返回旧值；
    } 
  } 
  ++ modCount的; 
  // 如果元素个数大于阈值，则扩容
  if (++size > threshold) 
    resize(); 
  afterNodeInsertion（驱逐）；
  返回空；
}

1.判断数组table[i]的键值对是否为空或null，否则执行resize()展开;

2.根据键值key，对插入的数组索引I计算hash值，如果table[i]==null，直接新建节点并添加。转6，如果table[i]不为空，转3;

3.判断table[i]的第一个元素是否与key相同。如果相同，则直接覆盖值。否则转4。这里相同指的是hashCode和equals;

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

5.遍历table[i]判断链表添加元素后的长度是否大于等于8，如果大于等于8，则将链表转化为红黑树，并执行in中的插入操作红黑树。否则，插入链表。如果遍历过程中key已经存在，直接覆盖value;

6.插入成功后，判断实际key value对数量size是否超过最大容量阈值。如果超过，请扩大容量。

获取值

public V get(Object key) { 
  Node<K,V> e; 
  返回 (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> 首先，e；国际n; Ｋ；
  // 哈希表中有内容，然后在哈希表中找到key的位置。
  if ((tab = table) != null && (n = tab.length) > 0 && 
      (first = tab[(n - 1) & hash]) != null) { 
    // 总是判断第一个节点是否是一个要找到。如果是，则返回
    if (first.hash == hash && // 始终检查第一个节点
        ((k = first.key) == key || (key != null && key.equals(k)))) 
      return first;    
      // 如果是红黑树，则转到红黑树
      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); 
    } 
  }
  返回空值；
}

Map中有内容。根据key的hash值，找到key所在的索引。

查找索引，判断第一个节点是否是要查找的节点，如果是则返回。

判断下面的节点是否是红黑树。如果是这样，去红黑树。

不是红黑树，遍历链表寻找。

如果未找到则返回 null

以上就是关于“应该知道的HashMap源码分析”的介绍，大家如果想了解更多相关知识，不妨来关注一下极悦的Java基础教程，里面的课程内容丰富，由浅到深，通俗易懂，很适合没有基础的小伙伴学习，希望对大家能够有所帮助。