关于java:Java基础HashMap-源码探究

37次阅读

共计 6477 个字符，预计需要花费 17 分钟才能阅读完成。

常常应用 Java 的 HashMap，但你有理解过其外部的实现原理么？数据是如何存储的？哈希抵触是如何解决的？
本篇文章将带你深刻源码探索 HashMap 的实现原理。

文档正文

HashMap 是 Map 接口的实现类，实现了所有可选的操作，并且容许 null key 和 null value。（能够简略的了解与 HashTable 性能雷同，除了它是不同步的，以及反对空值。）

存取效率：在存储的元素均匀分布在桶中时，get 和 put 元素的工夫不变。遍历的效率与 capacity 相干，因而如果重视遍历的效率，不要把 capacity 初始值设的很大，或把负载系数设的很小。

非同步：不要用多线程同时批改。

一、类定义

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

继承自 AbstractMap，并实现 Map、Cloneable、Serializable 接口。

一）实现的接口

Cloneable和 Serializabel 都是标识接口，外面没有办法定义。实现这种接口仅用于标识这个类应该有这中性能。

Map接口中定义了要实现的办法，并且给出了局部办法的实现。
https://blog.csdn.net/weixin_44203158/article/details/109340113

Q：接口外面能够实现办法么？
A：是能够的！
从 Java8 之后增加了这个性能，次要思考的是若接口发生变化，所有的实现类都要跟着进行批改。但有了接口能够实现办法后，就不必再改实现类了。
Q：接口中实现办法有 default 和 static 两种润饰？
A：用 default 润饰的叫默认办法，用 static 润饰的叫静态方法。default能够被重写，然而 static不行。
Q：实现多个接口的默认办法抵触怎么办？
A：在实现类中重写，且可调用接口中默认的办法。
Q：那为什么不必抽象类？
A：抽象类不能多继承。

二）继承的类

AbstractMap 抽象类提供对 Map 接口的根本实现，以加重实现 Map 接口的工作量。

对于不可变的 Map 实现类，只须要实现 entrySet() 办法。
对于可变的 Map 实现类，还须要实现 put()、remove() 等办法。

二、成员变量


    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

从变量和正文中能看出 HashMap 类的局部个性

  • 定义容量须要是 2 的次方数。因而示意的时候也用位运算来定义的
  • 默认负载达到 75% 时会扩容
  • 单个桶存的元素数大于 8 会变为树形存储，小于 6 改回列式存储
  • 当 capacity 大于 64 时，才会触发单节点的树形转换

容量为什么应用 2 的次方数？

在 HashMap 中采纳的是除留余数法，即 table[hash % length]
在古代 CPU 中求余是最慢的操作，所以人们想到一种奇妙的办法来优化它，即 length 为 2 的指数幂时，hash % length = hash & (length-1)
如何做到的？
https://www.cnblogs.com/sanzao/p/10245212.html
https://blog.csdn.net/u014540814/article/details/88354793

// 上面的代码用于调整容量，将容量调为下一个 2 次方数
// 简略来说应用了位运算的形式，将这个数第一个 1 前面的所有位都换为 1
static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

被标记为 transient 的变量

Q：transient 关键字是做什么的？
A：避免属性被序列化
Q：为什么要用 transient 润饰？
A：出于平安问题思考

transient Node<K,V>[] table;

三、重要外部类

一）Node

最重要的外部类 Node，定义了 HashMap 中的节点。


    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
      // ......
    }

留神到应用了泛型类

https://segmentfault.com/a/1190000002646193
Q：什么是泛型类？
A：类名 + 一对尖括号。person<X>。在 JDK 5 中呈现。
Q：为什么要用泛型类？
A：其中一个重要起因是为了创立 容器类。假如没有泛型，为了反对不同类型的容器，可能须要定义多个类来反对。但有了泛型能够只用定义一个。缩小了编码的冗余。
Q：泛型定义写在什么地位？
A：泛型类写到类名前面，泛型办法写到返回类型之前。
Q：泛型的类型是何时确定的？
A：应该是在编译时确定的。

有 4 个成员变量

final int hash;
final K key;
V value;
Node<K,V> next;

hashCode() 计算形式有些奇怪？

public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value); // 为什么要用异或运算符？}

四、重要函数

hash()

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

getNode()

这个外面体现了很多设计思维

  • first = tab[(n - 1) & hash] 从这里能够猜出来

    • hash 底层放到了一个数组外面
    • 容量设计为 2 的指数，在这里 n-1 二进制全是 1，不便做 & 运算

  • 在节点抵触时，会有两种检索抵触的形式。先判断是不是树节点，不是才程序遍历

      final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (first = tab[(n - 1) & hash]) != null) {
          if (first.hash == hash && // always check first node
              ((k = first.key) == key || (key != null && key.equals(k))))
              return first;
          if ((e = first.next) != null) {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);
          }
      }
      return null;
  }

putVal()

插入数据

  • 表的空容量判断
  • 桶上如果没有元素，间接新建

  • 桶上如果已有元素

    • 先判断 key 值是否存在，如果存在则将要替换 value
    • 如果是树结构，依照树的形式解决
    • 如果是列表构造，遍历看是否有 key 雷同的

  • 若须要新建 Node 节点

    • 树转换的计数 + 1
    • table 存储量 + 1，若大于 threshold 则 resize()
      final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
      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 {
          Node<K,V> e; K k;
          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);
                      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;
              }
          }
          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()

    在扩容时会调用的函数

    // 扩容时会依照 2 倍的形式扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
       oldCap >= DEFAULT_INITIAL_CAPACITY)
  newThr = oldThr << 1; // double threshold

// 重新整理数据
for (int j = 0; j < oldCap; ++j) {
  Node<K,V> e;
  if ((e = oldTab[j]) != null) {oldTab[j] = null;
      if (e.next == null)
          // 如果该节点没有 hash 抵触，则放到原位或者 2 倍的地位
          newTab[e.hash & (newCap - 1)] = e;
      else if (e instanceof TreeNode)
          // 如果有 hash 抵触，且抵触很多（用树状存储），会进行拆分
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
      else { // preserve order
          // 有 hash 抵触，用列表寄存，整体放到 [j + oldCap] 地位上
          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;
          }
      }
  }
}

    treeifyBin()

      final void treeifyBin(Node<K,V>[] tab, int hash) {
      int n, index; Node<K,V> e;
      // 如果 table 自身容量还很小，先应用扩容
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
          resize();
      else if ((e = tab[index = (n - 1) & hash]) != null) {
          TreeNode<K,V> hd = null, tl = null;
          do {
              // 其实是调用 LinkedHashMap 构造方法，TreeNode 也是 LinkedHashMap 扩大而来
              TreeNode<K,V> p = replacementTreeNode(e, null);
              // 这里是串成一个双向链表
              if (tl == null)
                  hd = p;
              else {
                  p.prev = tl;
                  tl.next = p;
              }
              tl = p;
          } while ((e = e.next) != null);
          if ((tab[index] = hd) != null)
              // 将链表转换成树（红黑树），暂不具体钻研了
              hd.treeify(tab);
      }
  }

    前面函数大同小异，可本人探索。

正文完
java
发表至： java
2022-10-12
 0
关于java:kubernetes-pvcontroller-解析
关于java:架构必问CDN-是什么为什么快
关于java:教你用-Java-写一个自己的-Tomcat-容器涨姿势了
关于java:如何根据对象的属性去重JDK-8-Stream-轻松搞定来长长见识