源码系列 之 HashMap

简介

  HashMap可能是Java程序员最常用的集合之一了，面试也是常考题之一。那么我们平时了解到的特性都是怎么来的呢，什么一会儿是链表，一会儿又是红黑树。八股文选手现在已经像高中背《滕王阁序》一样，肌肉反应似的在脑子背过一遍了，也不是说这样不好吧，只是我们需要知其所以然。接下来会给大家分享一下基于 JDK 1.8的HashMap的源码。可能并不适合才开始学习HashMap的同学，需要一定的基础。JDK 1.8 中的 HashMap 共2425行代码，其中包含13个成员变量，51个成员方法和14个内部类。 接下来会给大家展开讲讲。

HashMap的一些特点

  在正式讲源码前，我们先回顾一下HashMap的一些八股文特点，我们可能带着这些特点去看源码，可以有一种原来如此的感觉：

• HashMap是不支持线程同步的，也就是线程不安全的。
• HashMap 的key值最多只能存一个null值，而values可存多个null值。
• HashMap是无序的。
• 默认初始数组容量为16。
• HashMap的数组最大容量只会是2的N次幂。
• 会根据用户设置的初始容量值，向上查找最小的2的N次幂。
• 在 JDK 1.8 中新加了红黑树结构，当链表的长度大于8，且数组长度大于64时，链表会转化为红黑树，以加快查找速度，因为链表的查找性能为O(n)，红黑树的查找性能为O(log(n))。
• HashMap容量达到数组最大容量的0.75倍时，就会发生扩容，容量变为原来的两倍 ，然后把原数据复制到新数组中去，扩容比较浪费时间，所以，我们可以在初始化时，尽可能的预估容量大小，减少扩容次数！
• 处理哈希冲突时，添加链表值时（还未使用红黑树），1.7是头插法，1.8是尾插法。
• 除了线程不安全和允许为空和HashTable用法没什么区别。

HashMap类结构

源码如下：

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

类结构图如下：

  我们这里可能看到，HashMap已经继承了AbstractMap，而AbstractMap类已经实现了Map接口，那为什么HashMap还要再实现Map接口呢？而且在ArrayList中LinkedList中也有类型的情况，这样不是多此一举吗？后来查证后得知，据创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写Java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样保存下来了。其实像这种历史遗留问题JDK中很多，有的是为了兼容，有的可能觉得没必要就不改了，所以我们大可不必畏惧源码，都是人写的，都可能会有错，有啥大不同，看一次不会，看十次还不会吗？
  这里我们理解再次实现Map接口为一个失误，就可以了。AbstractMap主要包括Map类型数据结构的常用操作，而Cloneable则表示HashMap是可以被克隆的，Serializable则表示HashMap可以被序列化。

HashMap的成员变量

  这里介绍一下HashMap的成员变量，有很多特性我们直接从成员变量上就能窥视一番。

• static final long serialVersionUID = 362498820763181265L;
  序列化时会用到的serialVersion值。
• static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  默认的table初始容量，即默认初始容量16 （一定是2的N次幂）。
• static final int MAXIMUM_CAPACITY = 1 << 30;
  表最大的容量，即2的30次方。
• static final float DEFAULT_LOAD_FACTOR = 0.75f;
  负载因子，用于扩容，默认为0.75。
• static final int TREEIFY_THRESHOLD = 8;
  链表长度大于该阈值转为红黑树。
• static final int UNTREEIFY_THRESHOLD = 6;
  当树的节点数小于等于该参数则转成链表，我们都知道1.8里，哈希冲突导致链表扩大到8后，会转化成红黑树，那你知道红黑树小于6会退化成链表吗？
• static final int MIN_TREEIFY_CAPACITY = 64;
  容器可以树状化的最小表容量，即HashMap的数组大于64，且单链表大于8，才会转化红黑树。
• transient Node<K,V>[] table;
  哈希中的数组，这里我们就可以看出，数组中存储的其实是Node元素，即完整的key和value，初始化时大小会根据用户设置的初始值向上取整为2的整数倍。
• transient Set<Map.Entry<K,V>> entrySet;
  保存缓存entrySet()。
• transient int size;
  表示当前HashMap包含的键值对数量。
• transient int modCount;
  表示当前HashMap修改次数，主要用于迭代的快速失败（可通过该值判断是否并发修改，如果并发修改直接抛出异常），例如put()一次就+1，但某个key对应的value值被覆盖不属于结构变化。
• int threshold;
  表示当前HashMap能够承受的最多的键值对数量，一旦超过这个数量HashMap就会进行扩容，等于当前最大容量 * loadFactor。
• float loadFactor;
  哈希表的加载因子。加载因子其实是可以大于1的，你知道吗？之所以不设这么大，是因为，这样哈希碰撞太大了，严重影响查询效率，0.75是权衡空间和查找时间的中优选择。
  所有成员变量如下图所求：
  

HashMap的成员方法

   以下是HashMap的成员方法，每个方法会大概提及一下，重要的方法会重点讲解一下。

• public HashMap(int initialCapacity, float loadFactor);
  构造函数，可以自行设置初始容量和负载因子，这里负载因子，可以大于1，可以小于0.75，可根据内存和响应时间，自行权衡选择。

  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;
      this.threshold = tableSizeFor(initialCapacity);
  }
  

• public HashMap(int initialCapacity);
  构造函数，可以自行设置初始容量值，负载因子为0.75。

• public HashMap();
  默认构造函数，初始容量为16，负载因子为0.75。

• public HashMap(Map<? extends K, ? extends V> m);
  构造函数，初始容量为16，负载因子为0.75，用与指定Map相同的映射结构，构造一个新的HashMap。

• static final int hash(Object key);
  ​ hash是求哈希值 + 扰动函数，是首先对key取hashCode值，然后扰动后，再作为hash值，这样可以使高位参与运算，减少哈希碰撞，使Node值分布的更加均匀，后面很多函数都会用到hash(Object key)方法计算哈希值。

static final int hash(Object key) {
    int h;
    // h = key.hashCode() 为第一步 取hashCode值
    // h ^ (h >>> 16)  为第二步 低16位与高16位做异或运算，使得之后在做&运算时，此时的低位实际上是高位与低位的结合，可大大增加随机性，减少了碰撞冲突的可能性
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

例如：当n为默认16时，tab[i = (n - 1) & hash] 用&判断节点该落在那个位置上时，不做扰动时，如果哈希值高位变化大，低位变化小，则很多值会落到同一位置，碰撞冲突就会很大。

• static Class<?> comparableClassFor(Object x);
  ​ 如果是" Class C implements Comparable "的形式，则返回x的类。
• static int compareComparables(Class<?> kc, Object k, Object x);
  ​ 如果x匹配kc，则返回k. compareto (x)，否则为0。
• static final int tableSizeFor(int cap);
  ​ 返回给定目标容量向上取的最小2的N次幂，比如给定7，向上取则为8，给定13，向上取则为16，通过位运算计算得出。

	static final int tableSizeFor(int cap) {
		// 先减一，是为了避免原本就是2的N次幂
        int n = cap - 1;
    	// 或操作，只要有一个1，结果则为1
        // 以下五步位运算操作，相当于把最高位到最后一位的数字全变成1
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        // 如果最后，n不小于0，且不大于等于MAXIMUM_CAPACITY，则返回n + 1,n + 1则是给定目标容量向上取的最小2的N次幂
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

• final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
  根据传入的Map，用Map.putAll新建一个map，是public HashMap(Map<? extends K, ? extends V> m)构造函数的实际执行者。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
      	// 如果当前数组为空，初始化阈值
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果不为空，且大于阈值，则扩容
        else if (s > threshold)
            resize();
      	// 扩容后，遍历增加所有值即可
        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);
        }
    }
}

• public int size();
  返回当前Hash集合的长度。
• public boolean isEmpty()
  返回当前hash集合是否为空。
• public V get(Object key);
  返回当前集合下key对应的value值，如果不存在该key，则返回为null，注意，返回为空不一定就是key不存在，也可能value值本来就为空。
• final Node<K,V> getNode(int hash, Object key);
  get(Object key)方法的实际执行者，主要通过key算出的哈希值确定在数组中的位置，然后再在树或者链表中进行查找，下面这段代码在源码中多处被用到，所以需要仔细阅读下:

// 传入key值算出的hash值，和key值
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 如果哈希数组不为空 且 长度大于0 且 hash值对应该的table[i]不为空，则进行查找，否则返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
    		// (n - 1) & hash 比单独取模快
        (first = tab[(n - 1) & hash]) != null) {
        // 如果对应table[i]第一个节点匹配，则直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果对应table[i]第一个节点不匹配，且next不为空，则继续匹配    
        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;
}

• public boolean containsKey(Object key)
  判断是否包含给定key值。直接调用getNode(int hash, Object key)，值不为null，则返回true。
• public V put(K key, V value)
  添加值操作，直接调用putVal(…)方法，可以说是整个HashMap的核心之一，下面会讲到。
• final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);
  ​ put(K key, V value)的具体实现，代码解析如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果tab没有初始化，则进行扩容初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果对应tab[i]为空，没有发生碰撞，则直接加入新节点    
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 发生碰撞进行如下操作    
        else {
            Node<K,V> e; K k;
            // 如果第一个节点匹配，则覆盖value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果不匹配，且为红黑树，则用红黑树的putTreeVal(...)方法操作
            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);
                        // 如果尾插后大于 TREEIFY_THRESHOLD ，则转化为红黑树
                        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;
            }
        }
        // 修改次数加1
        ++modCount;
        // size加1，如果超过threshold，则扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

​ 整个过程如下图所求：

• final Node<K,V>[] resize()
  ​ 扩容resize()就是重新计算容量并扩大，当HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是新建一个新数组，把原有值，全部“复制”到新数组中去，复制是一个很耗时的操作，所以我们在初始化时就应该尽可能的指定数组大小，以减少复制行为。

​ 代码解析如下：

		final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 如果不是第一次初始化，新容量为原来的两倍（<< 1）
        if (oldCap > 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) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 如果是第一次初始化，则用默认参数初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果newThr为0，则我们重新计算该值等于newCap * loadFactor;
        if (newThr == 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) {
        		// 把每个bucket都移动到新的buckets中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    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
                    		// 链表优化重hash的代码块
                        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;
                            }
                            // 原索引 + oldCap
                            // 1.8之后的扩容为原来的两部，无需重新计算hash值，可直接计算位置
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

• final void treeifyBin(Node<K,V>[] tab, int hash)
  替换给定哈希值下的bin中所有的链接节点，除非表太小，在这种情况下改为调整大小。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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 {
            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);
    }
}

• public void putAll(Map<? extends K, ? extends V> m);
  添加map中所有值，直接调用putMapEntries(Map<? extends K, ? extends V> m, boolean evict)方法。
• public V remove(Object key);
  ​ 删除节点操作，直接调用 removeNode() 方法。
• final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)
  删除节点操作，与getNode(int hash, Object key)方法类似，先找到指定节点，如果是树形结构，则用树形的删除操作，如果是链表结构则用链表的删除方式。

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;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
      	// 首先查找到该节点，和getNode(int hash, Object key)方法类似
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
          	// 如果是红黑树，则用树的查找方式，如果是链表，则直接遍历查找到为止
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
      	// 如果找到该节点，则进行删除操作，并返回该节点值
        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;
          	// 修改次数 + 1
            ++modCount;
          	// 尺寸 - 1
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

• public void clear()
  ​ 删除集合内所有元素。

	public void clear() {
        Node<K,V>[] tab;
        // 修改次数加1
        modCount++;
        if ((tab = table) != null && size > 0) {
            // 尺寸归0
            size = 0;
            // 释放所有链表或者红黑树，这些对象会在垃圾回收中被回收
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

• public boolean containsValue(Object value);
  查找集合Value中是否有某值。
• public Set<K> keySet();
  返回所有key的集合。
• public Collection<V> values()
  返回所有values的集合。
• public Set<Map.Entry<K,V>> entrySet()
  ​ 返回所有entry的集合 ，entry即包括key和对应的value值。
• public V getOrDefault(Object key, V defaultValue);
  ​ 查找key对应的值，如果不存在，则返回默认值，即传入的defaultValue。
• public V putIfAbsent(K key, V value);
  如果该值不存在，则存入，直接调用putVal(…)。
• public boolean remove(Object key, Object value);
  ​ 删除节点，直接调用removeNode(…)。
• public boolean replace(K key, V oldValue, V newValue);
  替换某节点，其实就是getNode(…)查找到该节点后，替换成功，返回true，失败返回false。
• public V replace(K key, V value)
  ​ 替换某节点，其实就是getNode(…)查找到该节点后，替换成功，返回该节点值，失败返回null。
• public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction);
  如果给定节点不存在，则用mappingFunction生成新的节点值。
• public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
  如果给定节点存在，则用remappingFunction进行计算，生成新的值。
• public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
  用给定节点值和remappingFunction进行计算，生成新的值，给定节点值不存在时，用null值计算。
• public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction);
  用remappingFunction函数，对key对应的值和参数value进行比较合并。
• public void forEach(BiConsumer<? super K, ? super V> action)
  遍历操作，可接受一个action，对集合中的元素进行操作。
• public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
  替换操作，可接受一个function，对集合中的元素进行操作。
• public Object clone();
  克隆一个HashMap，并返回

  	public Object clone() {
      HashMap<K,V> result;
      try {
          result = (HashMap<K,V>)super.clone();
      } catch (CloneNotSupportedException e) {
          // this shouldn't happen, since we are Cloneable
          throw new InternalError(e);
      }
      // 初始化一些信息
      result.reinitialize();
      // 加入当前集合所有元素
      result.putMapEntries(this, false);
      return result;
  }

• final float loadFactor();
  ​ 返回负载因子值。
• final int capacity()
  返回当前容量值。
• private void writeObject(java.io.ObjectOutputStream s);
  ​ 将HashMap保存到一个流中，序列化它。
• private void readObject(ObjectInputStream s)
  从流中读取HashMap，反序列化它。
• Node<K,V> newNode(int hash, K key, V value, Node<K,V> next)
  ​ 创建一个常规(非树)节点。
• Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next);
  ​ 用于从TreeNodes转换为普通节点。
• TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next)
  创建一个树节点。
• TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next);
  用于从TreeNodes转换为普通节点。
• void reinitialize()
  ​ 重置为初始默认状态。由clone和readObject调用。
• void afterNodeAccess(Node<K,V> p);
  允许LinkedHashMap post-action的回调。
• void afterNodeInsertion(boolean evict)
  ​ 允许LinkedHashMap post-action的回调。
• void afterNodeRemoval(Node<K,V> p);
  允许LinkedHashMap post-action的回调。
• void internalWriteEntries(java.io.ObjectOutputStream s);
  ​ 仅从writeObject调用，以确保兼容的排序。
  所有方法如下图所示
  
  

HashMap的内部类

  以下是HashMap的内部类。

• static class Node<K,V> implements Map.Entry<K,V>{…}
  最基本的HashMap的节点，单个节点的值就是存在这里面的。

  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; }
  
      public final int hashCode() {
          return Objects.hashCode(key) ^ Objects.hashCode(value);
      }
  
      public final V setValue(V newValue) {
          V oldValue = value;
          value = newValue;
          return oldValue;
      }
  
      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;
      }
  }
  

• final class KeySet extends AbstractSet<K>{…}
  继承AbstractSet抽象类，用于存储集合中的key值。

• final class Values extends AbstractCollection<V>{…}
  继承AbstractSet抽象类，用于存储集合中的values值。

• final class EntrySet extends AbstractSet<Map.Entry<K,V>>{…}
  继承AbstractSet抽象类，用于存储集合中的entry集合。

• private static final class UnsafeHolder{…}
  支持在反序列化期间重置最终字段。

• abstract class HashIterator{…}
  HashMap里通用的迭代器。

  abstract class HashIterator {
      Node<K,V> next;        // next entry to return
      Node<K,V> current;     // current entry
      int expectedModCount;  // for fast-fail
      int index;             // current slot
  
      HashIterator() {
          expectedModCount = modCount;
          Node<K,V>[] t = table;
          current = next = null;
          index = 0;
          if (t != null && size > 0) { // advance to first entry
              do {} while (index < t.length && (next = t[index++]) == null);
          }
      }
  
      public final boolean hasNext() {
          return next != null;
      }
  
      final Node<K,V> nextNode() {
          Node<K,V>[] t;
          Node<K,V> e = next;
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
          if (e == null)
              throw new NoSuchElementException();
          if ((next = (current = e).next) == null && (t = table) != null) {
              do {} while (index < t.length && (next = t[index++]) == null);
          }
          return e;
      }
  
      public final void remove() {
          Node<K,V> p = current;
          if (p == null)
              throw new IllegalStateException();
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
          current = null;
          K key = p.key;
          removeNode(hash(key), key, null, false, false);
          expectedModCount = modCount;
      }
  }
  

• final class KeyIterator extends HashIterator implements Iterator<K> {…}
  继承自HashIterator，用于key的迭代器。

• final class ValueIterator extends HashIterator implements Iterator<V>{…}
  继承自HashIterator，用于value的迭代器。

• final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>>{…}
  继承自HashIterator，用于entry的迭代器。

• static class HashMapSpliterator<K,V>{…}
  HashMap里通用的可分割迭代器，jdk 1.8 新加功能，用于并行遍历元素。

  static class HashMapSpliterator<K,V> {
      final HashMap<K,V> map;
      Node<K,V> current;          // current node
      int index;                  // current index, modified on advance/split
      int fence;                  // one past last index
      int est;                    // size estimate
      int expectedModCount;       // for comodification checks
  
      HashMapSpliterator(HashMap<K,V> m, int origin,
                         int fence, int est,
                         int expectedModCount) {
          this.map = m;
          this.index = origin;
          this.fence = fence;
          this.est = est;
          this.expectedModCount = expectedModCount;
      }
  
      final int getFence() { // initialize fence and size on first use
          int hi;
          if ((hi = fence) < 0) {
              HashMap<K,V> m = map;
              est = m.size;
              expectedModCount = m.modCount;
              Node<K,V>[] tab = m.table;
              hi = fence = (tab == null) ? 0 : tab.length;
          }
          return hi;
      }
  
      public final long estimateSize() {
          getFence(); // force init
          return (long) est;
      }
  }
  

• static final class KeySpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<K>{…}
  继承自HashMapSpliterator，用于key的可分割迭代器。

• static final class ValueSpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<V>{…}
  继承自HashMapSpliterator，用于value的可分割迭代器。

• static final class EntrySpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<V>{…}
  继承自HashMapSpliterator，用于entry的可分割迭代器。

• static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>{…}
  红黑树的树结构，操作相对复杂，之后会写一篇关于红黑树的文章，这点暂时不展开讲了。

  		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);
          }
  
          // 返回根节点
          final TreeNode<K,V> root() {
              ...
          }
  
          // 确保给定的根节点是其bin的第一个节点
          static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
              ...
          }
  
          // 查找节点
          final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
              ...
          }
  
          // 调用根查找节点
          final TreeNode<K,V> getTreeNode(int h, Object k) {
              ...
          }
  
          
          static int tieBreakOrder(Object a, Object b) {
              ...
          }
  
          // 形成从该节点链接的节点树
          final void treeify(Node<K,V>[] tab) {
              ...
          }
  
          // 把树节点转化成链表节点
          final Node<K,V> untreeify(HashMap<K,V> map) {
              ...
          }
  
          // 向树中加入新值
          final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                         int h, K k, V v) {
              ...
          }
  
          // 从树中删除值
          final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                    boolean movable) {
              ...
          }
  
          // 将树分裂成两颗树
          final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
              ...
          }
  
          /* ------------------------------------------------------------ */
          // Red-black tree methods, all adapted from CLR
  				
  				// 左旋
          static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                                TreeNode<K,V> p) {
              ...
          }
  
  				// 右旋
          static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                                 TreeNode<K,V> p) {
              ...
          }
  
          static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                      TreeNode<K,V> x) {
              ...
          }
  
          static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                     TreeNode<K,V> x) {
              ...
          }
  
          // 递归检查不变量
          static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
              ...
          }
      }
  

所有内部类如下图所求：

HashMap各种机制的实现

  除了刚刚的方法介绍以外，我觉得有些重要机制需要重点介绍下，具体请看下方。

初始化容量

   初始化会根据用户设置的初始容量值，向上查找最小的2的N次幂，具体请看上方 tableSizeFor(int cap) 方法的讲解。之所以容量取为2的N次幂，主要为了方便后面取模运算。

hash扰动函数方法

  扰动函数主要是为了让原有的哈希值变得更加的随机，这样节点能更加均匀的分布在数组中，我们在 hash(Object key) 方法中已讲的很清楚了，这里不再详述。

找到哈希桶索引位置

   在HashMap中找到哈希桶索引位置，总共分三步：

• 获取key的hashCode值
• 低位与高位做异或运算
• 取模运算

  前两步，已经在hash(Object key)里实现了，过程也讲清楚了，这里重点是取模操作，但是，直接取模运算的消耗是比较大的，HashMap中用了一个非常巧妙的方法，即：

h & (table.length -1)	

   而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。这里取模计算出索引i后，直接用table[i]，就可以找到该哈希值对应的位置了。

扩容

  扩容就是重新计算容量并扩大，当HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是新建一个新数组，把原有值，全部“复制”到新数组中去，复制是一个很耗时的操作，所以我们在初始化时就应该尽可能的指定数组大小，以减少复制行为，详细请看resize()详解。

线程不安全性

  在JDK 1.7下，多线程操作，可能会造成死循环问题，在JDK 1.8中不会，但仍然是线程不安全的操作，不建议使用，多线程并发，可以使用ConcurrentHashMap，之后会写一篇关于ConcurrentHashMap的源码分析，敬请期待。

jdk 1.7 版和 jdk 1.8 版的区别

• 1.7 底层数据结构是：数组+链表。1.8 底层数据结构是：数组+链表+红黑树结构（当链表长度大于8，且数组大于64，转为红黑树）。
• 1.7 中新增节点是头插法，1.8中新增节点是尾插法，尾插法也是1.8不易出现环型链表的原因。
• 1.7 扰动处理进行了9次 = 4次位运算 + 5次异或运算，1.8 扰动处理进行了2次 = 1次位运算 + 1次异或运算。
• 1.7 是插入数据前扩容，1.8是插入数据成功后扩容。
• 1.7 扩容后位置计算为：与原来一致，即：hashCode -> 扰动 -> 取模。1.8为更加高效，按扩容后的规律计算：扩容后的位置 = 原位置 or 原位置 + 旧容量。

与HashTable的区别

• 与之相比HashTable是线程安全的，且不允许key、value是null。
• HashTable默认容量是11。
• HashTable是直接使用key的hashCode(key.hashCode())作为hash值，不像HashMap内部使用static final int hash(Object key)扰动函数对key的hashCode进行扰动后作为hash值。
• HashTable取哈希桶下标是直接用模运算%，（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算），而HashMap所用的位运算会比单纯模运算快的多，基本是降维打击。
• 扩容时，新容量是原来的2倍+1。int newCapacity = (oldCapacity << 1) + 1 。
• Hashtable是Dictionary的子类同时也实现了Map接口，HashMap是Map接口的一个实现类。
  HashTable虽然是线程安全的，但是因为性能不行，现在基本已经不用了，如果需要线程安全的操作，我们可以使用ConcurrentHashMap。

参考资料

Java 8系列之重新认识HashMap