可以参考视频：


Java 7/8 HashMap源码详解

一、哈希表的简介

• 核心就是：基于哈希值的桶和链表。
  • 一般就是用数组来实现桶
  • 发生碰撞的时候，用链表来链接发生碰撞的元素

假设我们hash(x) = x % 16, 对下面所有元素进行hash并放入到hash表中。

• O(1)的平均查找、插入、删除时间.

• 致命缺点是哈希值的碰撞(collision)

  • 哈希碰撞：元素通过哈希函数计算后，会被映射到同一个桶中。上面的26, 126就发生了哈希碰撞。

二、JDK1.7 HashMap

对于HashMap的基本概念和在Java中的继承关系，相信都有一定的了解。
下面我只是对JDK 1.7 中不足的地方做简单分析。

1、构造方法

无参构造方法

// 默认初始化容量 2^4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子 0.75，用于计算阈值，进行扩容操作。选择0.75是一种在时间和空间上的折中选择 
// 如果当前哈希表中的元素个数 >= 容量 × 负载因子，就会进行扩容，否则可能就会发生严重的哈希碰撞
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 此处调用了含容量和负载因子的构造方法来进行初始化操作
public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

含容量的构造方法

 public HashMap(int initialCapacity) {// 调用了含容量和负载因子的构造方法来进行初始化操作，其中容量为传入的容量，负载因子为默认负载因子0.75this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

含容量和负载因子的构造方法

public HashMap(int initialCapacity, float loadFactor) {// 如果传入的初始化容量小于0，则抛出异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 如果传入的容量大于最大容量，就初始化为最大容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 如果负载因子小于0，或者是非法的浮点数，抛出异常if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// 根据传入的负载因子给负载因子赋值this.loadFactor = loadFactor;// int threshold// 阈值，容量×负载因子。目前大小为initialCapacity（还未扩容）// 超过阈值进行扩容操作threshold = initialCapacity;// 此处的init()方法是一个空方法，在向哈希表添加元素之前，不会真正地创建哈希表（以免占用过多的内存）init();
}// 空方法
void init() {
}

可见，无论调用哪种构造函数来初始化HashMap，最终调用的都是含容量和负载因子的构造方法，并且都没有真正的开辟出需要的内存空间。

2、添加方法

put()方法

// 空集合，用于判断表是否为空。Entry为hashMap的静态内部类
static final Entry<?,?>[] EMPTY_TABLE = {};public V put(K key, V value) {// 如果表是空的，就通过inflateTable()方法进行扩容if (table == EMPTY_TABLE) {// 等到真正向哈希表中添加元素时，才开辟内存空间inflateTable(threshold);}if (key == null)return putForNullKey(value);// 计算要插入元素的哈希值int hash = hash(key);// 根据哈希值来判断插入元素应该放在哪个桶中// 该方法决定了为什么哈希表的容量是2的幂int i = indexFor(hash, table.length);// 遍历哈希表for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;// 看待插入元素在哈希表中是否已近存在了，如果存在了，就进行覆盖操作if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;// 真正的添加操作，采用头插法，下面会单独来说addEntry(hash, key, value, i);return null;
}// 哈希表扩容函数
private void inflateTable(int toSize) {// Find a power of 2 >= toSize// 让容量向上舍入变为2的幂。比如toSize = 10 就会变为 16。int capacity = roundUpToPowerOf2(toSize);// 阈值，向上取整后的容量×负载因子 或 最大容量+1，取其中的较小值// 该变量在第一次放入操作时不会用到threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);// 根据capacity创建哈希表table = new Entry[capacity];// 创建了一个哈希种子，重构String的hash算法，在后面的潜在安全漏洞会谈到initHashSeedAsNeeded(capacity);
}private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";// 如果容量大于最大容量，就返回最大容量。// 否则调用Integer.highestOneBit()方法让其向上舍入为2的幂return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}// 通过一系列移位操作与异或操作获得元素的哈希值。 JDK 8 中已不再使用该方法
final int hash(Object k) {int h = hashSeed;// 如果哈希种子存在，并且进行哈希的元素的String类型if (0 != h && k instanceof String) {// 就让String使用另一种hash算法return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

为什么哈希表大小一定是2的幂？
要回答这个问题，我们需要先看看哈希表中一个重要的方法：static int indexFor(int h, int length)，该方法会根据插入元素的哈希值决定该元素应该被放在桶中。

static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";// 将传入的哈希值与其长度-1进行按位与操作，并返回其结果return h & (length-1);
}

对于哈希表，其实最致命的缺点就是哈希碰撞，也就是多个值会被放置在同一个桶中。最极端的碰撞如下：

想要避免发生哈希碰撞，就需要分别分到不同的桶中，对于indexFor函数中的h & (length - 1)就是这样一个操作，根据元素的哈希值和哈希表的长度-1来按位与，并且与运算的速度快，而且效率高。

如何体现出来呢？这和普通的 hash value = x % 10的优势在哪里？

当哈希表的大小长度为2的幂时，他的二进制表示是10000,让其中的长度-1之后就是1111。

当一个二进制与全为1的数进行按位与时，其结果就是等于 该数本身并且小于等于桶的最大数量，这样以来，只要数不同，那么他们按位与下来的值也就不同了，所以我们需要哈希表的容量为2的幂，这样可以提高计算效率。

如果是2的幂，可以理解为是一种截断，假设我们哈希长度还是16 ，按照indexFor运算。199的hash值是：

为什么使用位运算，而不是直接取模？

位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

addEntry()方法

void addEntry(int hash, K key, V value, int bucketIndex) {// 如果哈希表中的元素个数超过了阈值，并且该元素应该放入的桶中已经有了元素if ((size >= threshold) && (null != table[bucketIndex])) {// 进行扩容，扩容大小为原大小的2倍，以保证扩容后容量仍为2的幂// 并将扩容前哈希表中的元素全部重新计算哈希值，并放入到扩容后的桶中resize(2 * table.length);// 重新计算哈希值hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}// 创建节点，采用头插法将其放在对应的桶中createEntry(hash, key, value, bucketIndex);
}void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}// 扩容为新容量Entry[] newTable = new Entry[newCapacity];// 重新计算元素哈希值，再放入到扩容后的哈希表中transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;//重新计算阈值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;// 遍历原来哈希表中的元素for (Entry<K,V> e : table) {// 如果桶中元素不为空，就重新计算起哈希值，然后放入到扩容后的哈希表中while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];// 扩容转移时使用头插法newTable[i] = e;e = next;}}
}void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];// 将新节点放在桶的第一个位置，也就是采用头插法进行插入void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;}table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}

3、存在的问题

1 容易发生死锁
因为HashMap本身是线程不安全的，所以在多线程环境下，可能会发生死锁问题。JAVA HASHMAP多线程下的死循环

2 非常大的安全问题
和上文所提过的那样，HashMap可能会退化成一个单链表。
而且我们知道，HashMap是通过indexFor对对象计算出的hashcode值作为输入然后输出哈希表桶的位置，之后对桶后链表进行遍历，调用对象的equals方法，判断是要新建一个entry，还是在链表中存在相同的entry（当然，这里是通过key来判断的）。

String的哈希算法很容易就能产生多个哈希值相同字符串。所以，很可能很多的字符串就会放到同一个桶中，也就大概率会退化成单链表。

public int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];}hash = h;}return h;
}

但是，为了避免这种攻击，在 JDK 7 的哈希表中，重构了String类型计算哈希值的方法。

三、JDK1.8 HashMap

极端情况下， 有可能HashMap会退化成链表的形状 。这就违背了查询的高效性。而今天HashMap使用红黑树就是为了解决这个问题。
JDK1.8 HashMap不再使用数组 + 链表的方式，而是使用数组+ 链表 + 红黑树的方式。

1、红黑树TreeMap

基本介绍
一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑**（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍**，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。

性质

• 每个节点非红即黑
• 根节点（root）是黑的
• 不能有两个红色的节点连在一起（黑色可以）
• 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的
• 如果一个节点是红的，那么它的两儿子都是黑的
• 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点
• 每条路径都包含相同的黑节点

下面是HashMap中的结构

为什么用到了红黑树
让我们来看看注释

/*
HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表实现注意事项。链表结构（这里叫 bin ，箱子）Map通常充当一个binned（桶）的哈希表，但是当箱子变得太大时，它们就会被转换成TreeNodes的箱子，每个箱子的结构都类似于java.util.TreeMap。大多数方法都尝试使用普通的垃圾箱，但是在适用的情况下（只要检查一个节点的实例）就可以传递到TreeNode方法。可以像其他的一样遍历和使用TreeNodes，但是在过度填充的时候支持更快的查找然而，由于大多数正常使用的箱子没有过多的填充，所以在表方法的过程中，检查树箱的存在可能会被延迟。树箱(bins即所有的元素都是TreeNodes）主要是由hashCode来排序的，但是在特定的情况下，如果两个元素是相同的“实现了Comparable接口”，那么使用它们的比较方法排序。（我们通过反射来保守地检查泛型类型，以验证这一点——参见方法comparableClassFor）。使用树带来的额外复杂，是非常有价值的，因为能提供了最坏只有O(log n)的时间复杂度当键有不同的散列或可排序。因此,性能降低优雅地在意外或恶意使用hashCode()返回值的分布很差,以及许多key共享一个hashCode,只要他们是可比较的。（如果这两种方法都不适用，同时不采取任何预防措施，我们可能会在时间和空间上浪费大约两倍的时间。但是，唯一已知的案例源于糟糕的用户编程实践，这些实践已经非常缓慢，这几乎没有什么区别。）因为TreeNodes大小大约是普通节点的两倍，所以只有当容器包含足够的节点来保证使用时才使用它们（见treeifythreshold）。当它们变得太小（由于移除或调整大小），它们就会被转换回普通bins。在使用良好的用户hashcode的用法中，很少使用树箱。理想情况下，在随机的hashcode中，箱子中节点的频率遵循泊松分布（http://en.wikipedia.org/wiki/Poisson_distribution），默认大小调整阈值为0.75，但由于调整粒度的大小有很大的差异。忽略方差，list的长度 k=(exp(-0.5) * pow(0.5, k) / factorial(k))第一个值是:0:0.606530661:0.303265332:0.075816333:0.012636064:0.001579525:0.000157956:0.000013167:0.000000948:0.00000006more: less than 1 in ten million 如果再多的话，概率就小于十万分之一了树箱（tree bin很难翻译啊！）的根通常是它的第一个节点。然而，有时（目前只在Iterator.remove）中，根可能在其他地方，但是可以通过父链接（方法TreeNode.root()）恢复。所有适用的内部方法都接受散列码作为参数（通常由公共方法提供），允许它们在不重新计算用户hashcode的情况下调用彼此。大多数内部方法也接受一个“标签”参数，通常是当前表，但在调整或转换时可能是新的或旧的。当bin列表被树化、分割或取消时（ treeified, split, or untreeified），我们将它们保持在相同的相对存取/遍历顺序（例如字段Node.next）为了更好地保存位置，并稍微简化对调用迭代器的拆分和traversals的处理(splits and traversals that invoke iterator.remove)。当在插入中使用比较器时，为了在重新平衡中保持一个总排序（或者在这里需要的接近），我们将类和标识符码作为连接开关。由于子类LinkedHashMap的存在，普通(plain)与树模型(tree modes)之间的使用和转换变得复杂起来。请参阅下面的hook方法，这些方法在插入、删除和访问时被调用，允许LinkedHashMap内部结构保持独立于这些机制。（这还要求将Map实例传递给一些可能创建新节点的实用方法。）concurrent-programming-like SSA-based编码风格有助于避免在所有扭曲的指针操作中出现混叠错误。
*/

所以总结一下是：
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢

而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了** 查找数据快O(log n)，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当桶中元素大于8并且桶的个数大于64**的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

链表转红黑树体现了空间换时间的思想

2、属性

JDK1.8 中HashMap的属性

// 初始容量 16 (2的4次方)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子，默认为0.75，用于和容量一起决定扩容的阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 使用红黑树的阈值，当桶中的元素个数（链表长度）大于8时，才会使用红黑树进行存储
static final int TREEIFY_THRESHOLD = 8;// 使用链表的阈值，当桶中的元素个数小于6个时，就会由红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;// 最小的红黑树化的桶数，当桶的个数大于64个时，就会使用红黑树进行存储
static final int MIN_TREEIFY_CAPACITY = 64;// Node数组，也就是桶
transient Node<K, V>[] table;// 缓存entrySet
transient Set<Map.Entry<K,V>> entrySet;// map中k-v键值对的个数
transient int size;// 修改访问标记
transient int modCount;// 扩容阈值，等于 容量 × 负载因子，初始化时值为向上取2的幂
int threshold;// 负载因子
final float loadFactor;

3、存储的结构

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

4、构造方法

无参构造方法

public HashMap() {// 初始化了负载因子this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap(int initialCapacity)构造方法

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

HashMap(int initialCapacity, float 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;// 阈值，初始化时为传入容量取幂后的值this.threshold = tableSizeFor(initialCapacity);
}// 容量向上取整为2的幂
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;
}

5、添加方法

put(K, V)方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// 因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的
// 那么这种处理就可以有效避免类似情况下的哈希碰撞
static final int hash(Object key) {int h;// 如果key不为null，就让key的高16位和低16位取异或// 和Java 7 相比，hash算法确实简单了不少// 使用异或尽可能的减少碰撞return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}// 放入元素的操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab相当于哈希表Node<K,V>[] tab; Node<K,V> p; // n保存了桶的个数// i保存了应放在哪个桶中int n, i;// 如果还没初始化哈希表，就调用resize方法进行初始化操作// resize()方法在后面分析if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 这里的 (n - 1) & hash 相当于 Java 7 中的indexFor()方法，用于确定元素应该放在哪个桶中// (n - 1) & hash 有以下两个好处：1、放入的位置不会大于桶的个数（n-1全为1） 2、用到了hash值，确定其应放的对应的位置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 {// binCount用于计算桶中元素的个数for (int binCount = 0; ; ++binCount) {// 找到插入的位置（链表最后）if ((e = p.next) == null) {// 尾插法插入元素p.next = newNode(hash, key, value, null);// 如果桶中元素个数大于阈值，就会调用treeifyBin()方法将其结构改为红黑树(但不一定转换成功)if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 如果size大于阈值，就进行扩容操作if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

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（已近执行了put操作以后的扩容）if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 原容量扩大一倍后小于最大容量，那么newCap就为原容量扩大一倍，同时新阈值为老阈值的一倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 调用了含参构造方法的扩容// 原容量小于等于0，但是阈值大于0，那么新容量就位原来的阈值（阈值在调用构造函数时就会确定，但容量不会）else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 调用了无参构造方法的扩容操作else {               // zero initial threshold signifies using defaults// 如果连阈值也为0，那就调用的是无参构造方法，就执行初始化操作newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果新阈值为0，就初始化它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) {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// lo 和 hi 分别为两个链表，保存了原来一个桶中元素被拆分后的两个链表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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}}}}}return newTab;
}

图解扩容对链表的重构
比如哈希表中桶的个数是4个，其中0、4、8、12因为低两位都是0，与 4-1=3(11) 进行按位与后，都被放在了第一个桶中。

然后开始了扩容操作。将元素哈希值按位与旧容量（不是旧容量-1）为0的放在lo链表中，不为0的放在hi链表中。

do {next = e.next;// 当前元素的hash值和容量进行按位与，决定被分配到哪个链表中if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}
} while ((e = next) != null);

遍历链表，将lo中的放在原来的桶中，hi中的放在增加的桶中

// 通过头指针直接将链表放入桶中
if (loTail != null) {loTail.next = null;newTab[j] = loHead;
}
if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;
}

总结：

• 先将原桶中的元素的hash值与旧容量进行按位与操作

  • 如果结果为0，就放入lo链表中
  • 如果结果不为0，就放入hi链表中

• lo链表中的元素继续放在新的哈希表中原来的位置

• hi链表中的元素放在新的哈希表中，扩容后相对于原来的位置上(j+oldCap)

  • 两个桶之间的间隔数就为增加原来哈希表的容量
    好处

• 顺序放入，减少了发生死锁的几率

• 使得元素相对均匀地存在于哈希表中

5、putAll()方法

public void putAll(Map<? extends K, ? extends V> m) {putMapEntries(m, true);
}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {// 获得待插入表的大小int s = m.size();// 如果待插入表中有元素if (s > 0) {// 如果当前哈希表为空if (table == null) { // pre-size// 容量调整过程，如果超过阈值，就调用tableSizeFor()方法扩容(直接扩容，因为此时哈希表为空)float ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t > threshold)threshold = tableSizeFor(t);}// 超过阈值，就调用resize()方法扩容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);}}
}

这里用到了hash()，具体可以研究：知乎：hash()分析的最透彻的文章

6、移除方法

remove（Object key）

public V remove(Object key) {Node<K,V> e;// 调用removeNode()方法，返回其返回的结果return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}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;// 桶中有元素, p保存了桶中的首个元素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;// 找到对应的元素，保存在node中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;// 否则就不在指向这个元素elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

8、查找方法

get(Object key)方法

public V get(Object key) {Node<K,V> e;// 通过key的哈希值和key来进行查找return (e = getNode(hash(key), key)) == null ? null : e.value;
}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;// 如果第一个元素不是，就继续往后找。找到就返回，没至找到就返回nullif ((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;
}

9、HashMap中JDK1.8的树化方法

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果当前哈希表中桶的数目，小于最小树化容量，就调用resize()方法进行扩容if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();// 当桶中元素个数大于8，且桶的个数大于64时，进行树化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);}
}

链表变为红黑树的条件：元素个数大于8同时桶的个数大于64
推荐阅读：Hashmap链表长度为8时转换成红黑树，你知道为什么是8吗?
当某个桶中的元素个数大于8时，会调用 treeifyBin()方法，但并不一定就会变为红黑树
当哈希表中桶的个数大于64时，才会真正进行让其转化为红黑树

为什么桶中元素多于了8个，桶的个数小于64，调用resize()方法就可以进行调整？

因为调用resize()方法进行扩容时，会让同一个桶中的元素进行桶的重新分配。一部分会被放新哈希表中在原来的位置上，一部分会被放在扩容后的位置上。

为什么桶一定要大于64

以上就是文章的全部：
推荐阅读：
HashMap源码分析
【动图演示】重点！多图演示红黑树的概念及插入操作（附考研模拟题）