前言

本文将对HashMap（基于JDK1.8）的源码进行具体分析，包括构造方法以及增、删、改、查等基本操作。

源码分析

需要先了解的知识

将会用到的实例常量

1	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量，为2^4

1	static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量，为2^30

1	static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子

1	static final int TREEIFY_THRESHOLD = 8; //树化阀值

将会用到的实例变量

1	final float loadFactor; //加载因子

1	int threshold; //扩容的阀值，当键值对的数量超过这个阀值就扩容

/*
 * table（一般称为哈希桶）在首次使用时初始化，并根据需要调整大小。
 * 分配时，长度始终是2的幂（某些情况下可以为0）。
 */
transient Node<K,V>[] table;

1	transient int modCount; //HashMap被结构修改的次数

1	transient int size; //当前的键值对数量

Node（存储键值对的节点）

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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

	//每个节点的hashCode是将key和value的hashCode进行异或操作后得到的
    public final int hashCode() {	
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

	//设置新的value，返回旧的value
    public final V setValue(V newValue) {	
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

	//只有当两节点的key和value通过equals方法比较后都返回true时，equals方法才返回true
    public final boolean equals(Object o) {	
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

构造方法

HashMap的构造方法有4种。

默认的构造方法

  public HashMap() {
//加载因子设置为默认的0.75f
      this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  }

带一个Map类型参数的构造方法

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;	//加载因子设置为默认的0.75f
    putMapEntries(m, false);
}

该构造方法的作用是深拷贝一个HashMap

带一个int参数的构造方法

1
2
3

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

该构造方法的作用是深拷贝一个HashMap，具体看下putMapEntries方法

putMapEntries

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
     int s = m.size();	//s为传入Map的长度
     if (s > 0) {
         if (table == null) { //如果哈希桶为空，需先根据传入Map的长度指定扩容阀值
             float ft = ((float)s / loadFactor) + 1.0F;
	//如果ft小于最大容量（2^30），那么t等于ft，否则t等于最大容量
             int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                      (int)ft : MAXIMUM_CAPACITY);
	//指定扩容阀值
             if (t > threshold) {
		threshold = tableSizeFor(t);	
	}       
         } else if (s > threshold) {	//哈希桶不为空，且s大于扩容阀值
	//需扩容
	resize();	
}
         
//将传入Map的所有元素放入新创建的HashMap中
         for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
             K key = e.getKey();
             V value = e.getValue();
             putVal(hash(key), key, value, false, evict);
         }
     }
 }

带两个int参数的构造方法

/*
 * @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;		//初始化容量不能大于2^30
    if (loadFactor <= 0 || Float.isNaN(loadFactor))	//加载因子必须大于0
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;	//指定加载因子
    this.threshold = tableSizeFor(initialCapacity);		//根据指定初始容量获取扩容的阀值
}

下面来看下是如何通过初始容量来获取扩容阀值的

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;
}

最终返回的结果是一个大于或等于初始化容量的2^n，例如输入6，则返回8；输入16，则返回16。

put方法（增）

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put方法又调用了putVal方法，先看一下hash方法

  static final int hash(Object key) {
      int h;	
//h保存key的hashCode，最终返回的hash值是h和h无符号右移16位后的数进行异或操作
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

为什么要计算一个hash值，而不是直接用hashCode呢？

因为哈希桶容量通常是很小的，而hashCode是32位。所以在进行(n - 1) & hashCode这个运算时，通常只能用上低16位。这可能会导致键值对在哈希桶中的分布不均匀，一些桶的链表过长。所以无符号右移16位就相当于把高16位推到了低16位，再与低16位进行异或操作，并把结果作为hash值，就间接地利用了高16位，从而可以在一定程度上使得键值对分布更加均匀，降低hash冲突的概率。

putIfAbsent

put方法插入元素时，如果该元素已存在，会将旧的value替换为新的value（实现改的效果），如果不希望旧的value被替换，可以使用putIfAbsent方法。

@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

可以看出，该方法同样是调用了putVal方法。在看putVal方法之前，需要先了解resize方法。

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;		//新桶容量和新的扩容阀值初始化为0

      if (oldCap > 0) {	//如果旧桶容量大于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) {
	//如果旧桶容量为0，但旧的扩容阀值大于0，那么将新桶容量设置为该扩容阀值
	newCap = oldThr;
} else { 
	//如果旧的桶容量和扩容阀值都为0
          newCap = DEFAULT_INITIAL_CAPACITY;	//新桶容量设置为默认初始容量
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);	//新的扩容阀值设置为：默认初始容量*默认加载因子
      }

//如果此时新的扩容阀值为0，对应情况为：旧桶容量为0但旧的扩容阀值大于0
      if (newThr == 0) {	
          float ft = (float)newCap * loadFactor;	//ft为新桶容量*加载因子
	//当新桶容量和ft都小于最大容量时，新的扩容阀值为ft，否则为最大值
          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;	//e用于保存旧的节点
              if ((e = oldTab[j]) != null) {
                  oldTab[j] = null;	//将旧节点置空
			
                  if (e.next == null) {	//如果该节点后面没有节点（说明没有发生哈希冲突）
				/*
				 * 将当前节点放到新哈希桶的相应位置
				 *
				 * 注意：由于newCap的值为2^n，所以(newCap-1)与e.hash作与运算其实是一个
				 * 取模运算（e.hash对newCap取模），但这样写效率更高。
				 */
				newTab[e.hash & (newCap - 1)] = e;	
			} else if (e instanceof TreeNode) {	//如果当前节点是一棵红黑树
				//需要先将树拆分，然后再移动到新哈希桶中
				((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
			} else { 	//如果当前节点是一个节点数小于8的链表
			
				//将原链表拆分为两个链表（low链表和high链表）
                      Node<K,V> loHead = null, loTail = null;
                      Node<K,V> hiHead = null, hiTail = null;
                      Node<K,V> next;
				
                      do {	//当e不为null时执行该循环
                          next = e.next;
					
					//将当前节点的hash值与oldCap作与运算（有两种结果，0或oldCap，而且这两种结果出现的概率各占50%）
                          if ((e.hash & oldCap) == 0) {	//结果为0，加入low链表
                              if (loTail == null)
                                  loHead = e;
                              else
                                  loTail.next = e;
                              loTail = e;
                          } else {	//结果为oldCap，加入high链表							
                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);
				
				//将low链表存在原索引上
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;
                      }
				//将high链表存在原索引加上旧桶容量上
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }

//返回新的哈希桶
      return newTab;
  }

总共包含以下几个步骤：

获取新哈希桶的容量，更新扩容阀值
创建新哈希桶，并更新哈希桶
将旧哈希桶中的所以节点移动到新哈希桶上
返回新的哈希桶

putVal

  /**
   * Implements Map.put and related methods
   *
   * @param hash hash for key
   * @param key the key
   * @param value the value to put
   * @param onlyIfAbsent if true, don't change existing value
   * @param evict if false, the table is in creation mode.
   * @return previous value, or null if none
   */
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
      Node<K,V>[] tab; Node<K,V> p; int n, i;

//当哈希桶为空或其长度为0时
      if ((tab = table) == null || (n = tab.length) == 0) {
	//在resize方法中初始化哈希桶，并且将其长度赋给n
	n = (tab = resize()).length;	
}	
          
//i为新节点的索引，如果该索引对应的节点为空，说明没有哈希冲突，直接创建一个新节点
      if ((p = tab[i = (n - 1) & hash]) == null) {
	tab[i] = newNode(hash, key, value, null);
} else {	//发生哈希冲突
          
	Node<K,V> e; 	//e用于存储已存在的节点	
	K k;
	
	//p为新节点索引对应的原节点，k为p的key
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k)))) {	
		/*
		 * 如果p的哈希值和新节点相等，并且p的key和新节点的key通过equals方法比较后返回true，
		 * 说明新节点已存在。
		 */
		e = p;	
	} else if (p instanceof TreeNode) {
		//如果p节点为红黑树
		e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
	} else {
		//此时p节点为链表，将新节点放到链表的末尾
              for (int binCount = 0; ; ++binCount) {
                  if ((e = p.next) == null) {
                      p.next = newNode(hash, key, value, null);
				//当链表的长度大于等于树化阀值（8）时，将链表转化为红黑树
                      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不为空，说明新节点已存在
          if (e != null) { 
              V oldValue = e.value;
              if (!onlyIfAbsent || oldValue == null) {
			//如果onlyIfAbsent为false或者旧的value为null，更新节点的value
			e.value = value;	
		}                   
              afterNodeAccess(e);
              return oldValue;	//返回旧值
          }
      }

      ++modCount;		//结构修改次数加一
      if (++size > threshold) {	//当前键值对数量大于扩容阀值的时候
	//进行扩容操作
	resize();
}	           
      afterNodeInsertion(evict);
      return null;	//新加入的节点不重复时返回null
  }

putVal方法的执行步骤如下：

先判断哈希桶是否有初始化，没有初始化的话先初始化（所以哈希桶的初始化是发生在第一次添加元素的时候，之所以不在HashMap初始化的时候为哈希桶分配空间，是为了防止只创建集合而不添加元素时造成的空间浪费）
根据插入元素的hash值寻找相应的位置，判断该位置是否为空，为空则直接创建节点并插入，不为空时：
1. 判断是否存在相等的key
2. 判断该位置存储的是红黑树还是链表，根据不同情况有不同的插入
3. 插入完成后，如果key相等，则判断是否要替换value，并返回旧的value。
更新修改次数、当前键值对数量。如果当前键值对数量超过了扩容阀值，则进行扩容操作。
能够执行到最后，说明插入的键值对是新的，没有旧value，所以返回null。

remove方法（删）

remove有两个重载方法：

删除指定key的remove方法，如果删除成功，返回删除键值对的value，否则返回null。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

删除指定键值对的remove，如果删除成功，返回true，否则返回false。

@Override
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

这两个方法都是调用了removeNode方法

removeNode

  /**
   * Implements Map.remove and related methods
   *
   * @param hash hash for key
   * @param key the key
   * @param value the value to match if matchValue, else ignored
   * @param matchValue if true only remove if value is equal
   * @param movable if false do not move other nodes while removing
   * @return the node, or null if none
   */
  final Node<K,V> removeNode(int hash, Object key, Object value,
                             boolean matchValue, boolean movable) {
      Node<K,V>[] tab; Node<K,V> p; int n, index;
//tab用于存储哈希桶，n存储哈希桶的容量,index存储hash值对应的哈希桶索引,p存储hash值所对应的头节点

//如果哈希桶不为空且长度大于0，并且该key存在对应的节点，才会执行删除操作，否则直接返回null
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (p = tab[index = (n - 1) & hash]) != null) {
		
          Node<K,V> node = null, e; 	//node存储要删除结点
	K k; V v;	//k存储p节点对应的key
	
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k)))) {
		//如果要删除的节点的hash值和key都与p节点相等
		node = p;	
	} else if ((e = p.next) != null) {
              if (p instanceof TreeNode)	//如果p节点是红黑树
                  node = ((TreeNode<K,V>)p).getTreeNode(hash, key);	
              else {	//p节点是单链表
                  do {
                      if (e.hash == hash &&
                          ((k = e.key) == key ||
                           (key != null && key.equals(k)))) {
                          node = e;
                          break;
                      }
                      p = e;	//p记录要删除节点的上一节点
                  } while ((e = e.next) != null);
              }
          }
	
	//如果找到了要删除的节点（如果还指明了要删除的value的话，还要比较value是否一致）
          if (node != null && (!matchValue || (v = node.value) == value ||
                               (value != null && value.equals(v)))) {
              if (node instanceof TreeNode) {	//删除红黑树中的节点
			((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
		} else if (node == p) {	//要删除节点是链表的头结点
			tab[index] = node.next;
		} else {	//要删除节点不是链表的头结点
			p.next = node.next;
		}
                  
              ++modCount;	//增加修改次数
              --size;		//减少哈希桶的容量
              afterNodeRemoval(node);	
              return node;	//返回删除节点
          }
      }
      return null;
  }

删除节点的步骤如下：

先要确保哈希桶不为空且长度大于0，并且要删除的key在哈希桶中有对应节点。如果不满足这些条件，直接返回null。
如果对应节点就是要删除的节点，那么直接记录下该节点。如果不是的话，还要判断对应节点是红黑树还是单链表，分情况找到要删除的节点。
如果最终没有找到要删除的节点，返回null。如果找到了要删除的节点，就把该节点从红黑树或链表中删除，并返回该节点。

replace方法（改）

replace有两个重载方法

带三个参数的重载方法传入要修改的键值对的key和value，以及要更新后的value。如果找到该键值对并修改成功，返回true，否则返回false。

  @Override
  public boolean replace(K key, V oldValue, V newValue) {
      Node<K,V> e; V v;	//e存储要修改的节点，v存储修改节点的旧value

//如果找到要修改的节点并且该节点的value和oldValue一致，执行修改操作，否则直接返回false
      if ((e = getNode(hash(key), key)) != null &&
          ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {				
          e.value = newValue;		//更新该节点的value
          afterNodeAccess(e);
          return true;
      }
      return false;
  }

带两个参数的重载方法传入要修改的键值对的key以及更新后的value。如果修改成功，返回旧的value，否则返回null。

  @Override
  public V replace(K key, V value) {
      Node<K,V> e;
//如果找到要修改的节点，执行修改操作，否则直接返回null
      if ((e = getNode(hash(key), key)) != null) {
          V oldValue = e.value;	
          e.value = value;	//更新该节点的value
          afterNodeAccess(e);
          return oldValue;	//返回该节点的旧value
      }
      return null;
  }

这两个重载方法都调用了getNode方法

getNode

getNode方法的作用是根据传入的hash值和key值，找到对应的节点并返回，若没有找到则返回null。

  /**
   * Implements Map.get and related methods
   *
   * @param hash hash for key
   * @param key the key
   * @return the node, or null if none
   */
  final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; 	//tab存储哈希桶，first存储hash值所对应的头节点
int n; K k;		//n存储哈希桶容量

/*
 * 当哈希桶不为空并且其长度大于0，同时存在要查找的hash值所对应的头节点时，
 * 才执行相关查找操作，否则直接返回null。
 */
      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 ((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;
  }

get方法（查）

  public V get(Object key) {
      Node<K,V> e;
//如果找到对应节点，则返回该节点的value，否则返回null。
      return (e = getNode(hash(key), key)) == null ? null : e.value;
  }

可以看到，get方法也是通过getNode方法来查找节点。在分析replace方法时已经分析过该方法，这里不再多说。

小结

本文对HashMap的构造方法以及增删改查等基本操作进行了源码分析，分析过后，对于HashMap有了更深的认识，在这里小结一下：

HashMap有4种构造方法，除了默认的方法外，我们还可以通过其他的构造方法初始化HashMap的元素，或者根据需要设置哈希桶的初始化容量和加载因子。
哈希桶的初始化不是发生在创建HashMap的时候，而是发生在第一次插入元素的时候，通过扩容操作初始化。
哈希桶在扩容时，如果旧桶容量大于0并且小于最大容量（2^30），那么新桶容量是旧桶容量的两倍。旧桶中的链表会被拆分为两个链表存到新桶中。
哈希桶的数据结构是数组，在处理哈希冲突时，如果发生冲突的元素小于8个的时候，是用单链表存起来的。一旦冲突的元素个数大于等于8个，那么单链表将转化为红黑树。

HashMap源码分析（JDK1.8）

前言