乐趣区

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

常常应用 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,并实现 MapCloneableSerializable 接口。

一)实现的接口

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

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

Q:接口外面能够实现办法么?
A:是能够的!
从 Java8 之后增加了这个性能,次要思考的是若接口发生变化,所有的实现类都要跟着进行批改。但有了接口能够实现办法后,就不必再改实现类了。
Q:接口中实现办法有 defaultstatic 两种润饰?
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);
          }
      }

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

退出移动版