HashMap源码解析

本文主要通过对JDK 8中HashMap源码中的主要常量、主要成员变量、静态内部类、静态方法、构造方法以及常用的方法等几个方面进行分析，以了解HashMap的工作原理。

HashMap中的常量

   /**
    * The default initial capacity - MUST be a power of two.
    * 默认初始化容量 —— 16
    */
   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.
    * 最大容量 2^30 大约十亿
    */
   static final int MAXIMUM_CAPACITY = 1 << 30;
   /**
    * The load factor used when none specified in constructor.
    * 默认加载因子 0.75
    */
   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.
    * 发生树化时的最小容量，当哈希表的容量未达到64时，如果链表的长度过长，则会调整哈希表的大小
    */
   static final int MIN_TREEIFY_CAPACITY = 64;

主要成员变量

可以发现loadFactor(加载因子)使用final进行了修饰，也就是说加载因子一旦确定就不能被改变。

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     * 内部的数组，元素是Hash.Node，在第一次被使用时初始化（第一次向HashMap中存放元素时会被初始化），在必要的时候会进行扩容，容量永远是2的次方
     */
    transient Node<K,V>[] table;
    /**
     * The number of key-value mappings contained in this map.
     * key-value键值对的数量
     */
    transient int size;
    /**
     * The next size value at which to resize (capacity * load factor).
     *  下次扩容的阈值(当前容量 * 加载因子)
     */
    int threshold;
    /**
     * The load factor for the hash table.
     *  加载因子
     * @serial
     */
    final float loadFactor;

HashMap中的静态内部类

这部分主要关注HaspMap中的两种节点（基本节点、以及链表转换为红黑树后的节点），并且在这一部分我只关注这些内部类中的成员变量和一些基本的方法。

• 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> {
  			// hash和key被final修饰，因此hash和key是不能被修改的
  	       final int hash;
  	       final K key;
  	       V value;
  	       // 当由于哈希冲突形成链表时，next指向下一个节点
  	       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;
  	       }
  	
  	       ......
  	   }
  

• HashMap中的红黑树节点

  	/**
  	 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
  	 * extends Node) so can be used as extension of either regular or
  	 * linked node.
  	 * 继承了LinkedHashMap中的Entey,而LinkedHashMap中的Entey又继承了HashMap.Node
  	 */
  	static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  		// 父节点
  	    TreeNode<K,V> parent;  // red-black tree links
  	    // 左子树
  	    TreeNode<K,V> left;
  	    // 右子树
  	    TreeNode<K,V> right;
  	    // 当前链表的上一个节点
  	    TreeNode<K,V> prev;    // needed to unlink next upon deletion
  	    boolean red;
  	    TreeNode(int hash, K key, V val, Node<K,V> next) {
  	        super(hash, key, val, next);
  	    }
  	}
  

HashMap中的静态方法

• hash(Object key)
  又称散列函数，这里通过将key的hashCode的高16位与低16位进行异或得到一个散列值。特别需要注意的事，当key为null的时候得到的散列值为0，key为null的节点在被放置时会被放置到底层数组下标为0的位置上。

  static final int hash(Object key) {
  	int h;
  	/*
  		1. 当key为 null时，得到的结果是0，也就是说把key=null的值 放入哈希表中时，
  			一定会存放到index = 0的位置
  		2. 将key的哈希值 高16位 与 低16位 进行 异或 运算得到的值作为结果。
  	*/
  	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

• tableSizeFor(int cap)
  这个方法根据指定容量的大小返回实际容量的值（实际容量的值应该是一个正好大于等于指定容量大小的二的整数次方）

  /**
   * Returns a power of two size for the given target capacity.
   * 根据给定的容量大小 返回一个2的次方(正好大于等于给定的容量值)
   */
  static final int tableSizeFor(int cap) {
      /*
      * 实际上就是将cap-1转换为二进制数后，将其从第左边一位不为0的数开始，到最右边全部变为1 再加1
      * 例如14(1110) 减一后 13(1101) -> 15(1111) -> +1 = 16(10000)
      * 为什么要先减1? 如果不减1，16计算出来的容量即为32，浪费了空间
      *
      * */
      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;
  }
  

HashMap中的常用构造方法

	/**
     * 给定加载因子和初始容量的构造方法
     * @param initialCapacity   初始容量
     * @param loadFactor    加载因子
     */
    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;
        // 此时 底层的数据 并没有被初始化，在第一次被使用时，才会被初始化，
		// 设置下次扩容的阈值，在第一次向HashMap中存放元素时，会进行初始化，初始化容量的大小即为此时threshold的大小
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 传入指定初始化容量，调用 HashMap(int initialCapacity, float loadFactor) 构造方法
     * 默认的加载因子为0.75
     * @param initialCapacity 初始化容量
     */
    public HashMap(int initialCapacity) {
        // 默认加载因子0.75
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
	/**
     * HashMap的无参构造方法
     * 只是设置了加载因子为默认的0.75
     * 使用这个构造函数生成的HashMap，其内部的数组在初始化时的大小为默认的16
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

HashMap常用的成员方法

• get，在这一部分主要介绍与get()方法以及与getNode()方法。

  /**
   * 经常使用到的get方法,通过传入的key获取对应的value值
   * @param key
   * @return 查询到的节点值
   */
  public V get(Object key) {
      Node<K,V> e;
      // hash(key) 散列函数计算出一个hash值
      // 根据计算出的hash值去查找是否有这个节点，若无,则返回null,有就返回节点的value
      return (e = getNode(hash(key), key)) == null ? null : e.value;
  }
  
  /**
   * 根据散列函数计算的hash值和key的值 获取节点
   * @param hash hash(key)
   * @param key  key
   * @return 查询到的节点值
   */
  final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      // table != null && table.length > 0
          // 判断此时底层数组是否已经创建 且 底层数组中是否有数据
      // tab[(n - 1) & hash]) != null
          // 判断hash对应的底层数组中的索引位置处是否有节点
          // (n - 1) & hash 这实际上就是根据hash去计算其在底层数组中的索引值
          // 相当于 hash % table.length
      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) {
              // 判断数组上的节点指向的第一个节点是否是红黑树节点
              // 若是则直接调用红黑树中查找节点的方法，并返回 时间复杂度 O(logn)
              if (first instanceof TreeNode)
                  return ((TreeNode<K,V>)first).getTreeNode(hash, key);
              // 数组上的节点指向的第一个节点是普通节点 也就说底下是链表结构
              // 遍历链表 查找节点 时间复杂度 O(n)
              do {
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      return e;
              } while ((e = e.next) != null);
          }
      }
      return null;
  }
  

• put，在这一部分主要介绍与get()方法以及与putVal()方法。

  /**
   *  向Map中放入键值对，若要放入的键值对已存在，则替换值，并返回之前的值
   */
  public V put(K key, V value) {
  	// 调用putVal方法
      return putVal(hash(key), key, value, false, true);
  }
  
  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)
          // 此时，当底层数组还未初始化时 进入了这个if中 会调用resize()方法初始化数组
          n = (tab = resize()).length;
  
      // (n - 1) & hash 计算出该key对应的节点应该在数组上应该放置的位置
      // 如果 该位置上并没有节点存在 此时将该hash key value封装为一个新节点 并放置在该位置
      if ((p = tab[i = (n - 1) & hash]) == null)
          tab[i] = newNode(hash, key, value, null);
  
      // 该位置上有节点存在
      else {
          // 这里有个临时变量e，此时e为 null
          Node<K,V> e; K k;
          // 判断数组当前索引位置上的节点的key 是否与要存放的键值对的key相同，若相同则将让e指向该节点
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k))))
              e = p;
          // 数组当前索引位置上的节点的key 与要存放的键值对的key不同
          // 判断数组当前索引位置上的节点是否是红黑树节点
              // 若是则在红黑树中查找该节点
                  // 若查找的到则让 e 指向该节点
                  // 若红黑树中没有查找到 则将键值对添加至红黑树中
          else if (p instanceof TreeNode)
              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  
          // 数组当前索引位置上的节点不是红黑树节点
          else {
              // 遍历链表 若链表中能查到对应的节点，则将让e指向这个节点，若没有，则新建节点并添加到链表的尾部
              // JDK 8 改为尾插法 之前是 头插法
              for (int binCount = 0; ; ++binCount) {
                  if ((e = p.next) == null) {
                      p.next = newNode(hash, key, value, null);
                      // 添加新节点后 如果此时链表（加上数组上的节点）的长度大于等于8
                      // 则调用树化方法treeifyBin()，让该链表转化为红黑树
                      // 但是，在该方法中可以发现 当底层数组的长度小于64时
                      // 并不会进行树化操作，而会对哈希表进行扩容操作
                      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不为null 则说明 在HashMap中原先就存在这个key对应的节点
          // 那么将这个节点的值修改为传入的value 并将旧值返回
          if (e != null) { // existing mapping for key
              // 获取旧值
              V oldValue = e.value;
              if (!onlyIfAbsent || oldValue == null)
                  // 修改该key的值
                  e.value = value;
              afterNodeAccess(e);
              // 返回旧值
              return oldValue;
          }
      }
      // 如果能执行到此处，则说明HashMap原先并不存在与key对应的节点，执行了新增操作
      ++modCount;
      // 插入新节点后，若此时HashMap中的节点数量 大于 扩容阈值 则进行扩容操作
      if (++size > threshold)
          resize();
      afterNodeInsertion(evict);
      // 返回null
      return null;
  }
  

• resize，HashMap的扩容算法，非常重要的方法，扩容后的底层数组长度是之前的两倍

  final Node<K,V>[] resize() {
      // 扩容前的底层数组
      Node<K,V>[] oldTab = table;
      // 定义了一个oldCap 变量 用来记录扩容前底层数组的容量
      // 若是此时底层数组还未初始化 则定义为0
      int oldCap = (oldTab == null) ? 0 : oldTab.length;
      // 保存扩容前的阈值
      int oldThr = threshold;
      int newCap, newThr = 0;
      // 判断扩容前的容量是否大于 0
      // 也就是判断现在是不是在初始化底层数组
      if (oldCap > 0) {
          // 如果扩容前的底层数组的容量 >= HashMap的最大容量 不再进行扩容
          if (oldCap >= MAXIMUM_CAPACITY) {
              // 将扩容阈值设置为Integer的最大值
              threshold = Integer.MAX_VALUE;
              // 直接返回扩容前的底层数组
              return oldTab;
          }
  
          // 扩容后数组的容量 = 扩容前数组容量 * 2
          // 若扩容后数组的容量小于 最大容量 并且扩容前的容量大于等于16
          // 定义新的扩容阈值为原来扩容阈值的两倍
          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
              // 扩容后的扩容阈值即为 之前的扩容阈值 * 2
              newThr = oldThr << 1; // double threshold
      }
      else if (oldThr > 0) // initial capacity was placed in threshold
      	// 这个if代码块中的操作就是在对底层数组初始化
     		// oldThr > 0 条件 是在判断是否在构造函数中传入了初始容量，只有定义了初始容量时 才会给扩容阈值赋值，否则默认为0
          newCap = oldThr;
      else {               // zero initial threshold signifies using defaults
          // 在构造函数中未传入初始容量，使用默认初始容量
          // 初始化后的容量也就是16
          newCap = DEFAULT_INITIAL_CAPACITY;
          // 下次的扩容阈值也就是 16*0.75 = 12
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
      }
      if (newThr == 0) {
      	// 这个代码块中还是初始化操作
          // 在构造函数中传入了初始容量时 的初始化操作会进入这个代码块
          float ft = (float)newCap * loadFactor;
          // 如果初始化的容量小于 最大容量 并且 扩容阈值也小于 最大容量，那么扩容阈值 = 初始容量 * 加载因子
          // 否则 直接将 扩容阈值 设置为 Integer的最大值 ，也就是说 不会在进行扩容操作了
          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) {
              // 当前索引处有节点存在
                  // 将当前索引位置的引用置为null,等待gc
                  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;
                          // 将这条链表上的节点 分为两部分搬移到新的数组中(为什么要分为两部分？可以减少查询的效率)
                          // 这部分有些抽象，先通过例子来理解会容易很多
                          // 假设此时 oldCap = 4，当前索引值为 1
                          // hash值的取值范围即为 1,5,9,13,17...
                          // 以1开始的差值为4的等差数列，1的二进制数为0001,4的二进制数为0100,因此所有的hash值的二进制数的第三位(从右往左数)不是0就是1，通过这个方法可以把当前链表上的节点分成两部分
                          // 扩容后新数组的容量为 8
                          if ((e.hash & oldCap) == 0) {
                          	// 保存 hash值二进制数的第三位(从右往左数) 为0 的节点
                              if (loTail == null)
                                  loHead = e;
                              else
                                  loTail.next = e;
                              loTail = e;
                          }
                          else {
                          	// 保存 hash值二进制数的第三位(从右往左数) 为1 的节点
                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);
                      // hash值二进制数的第三位(从右往左数) 为0 的节点直接搬移到新数组的当前索引处
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;
                      }
                      // hash值二进制数的第三位(从右往左数) 为1 的节点直接搬移到新数组的 当前索引 + 旧数组容量 处
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }
  

未完待续…