本文主要是介绍深读源码-java集合之HashMap源码分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
简介
HashMap采用key/value存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序；
继承体系
HashMap实现了Cloneable，可以被克隆。
HashMap实现了Serializable，可以被序列化。
HashMap继承自AbstractMap，实现了Map接口，具有Map的所有功能。
存储结构
在Java中，HashMap的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。（严谨的说法是每一个键也叫一个桶）
在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。
当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。
数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。
本人开始不太理解，查阅整理了相关资料，大家学习的时候可以参考
陌隋笔记：
底层存储结构：
哈希冲突的解决方式有很多：
● 开放定址法
● 再哈希法
● 链地址法（拉链法）
● 建立公共溢出区
HashMap采用的是拉链法解决冲突：
拉链法就是将链表和数组结合。也就是创建一个链表数组，数组中的每一格就是一个链表。若遇到哈希冲突，得到数组下标，把数据放在对应下标元素的链表上即可。
1.数组
HashMap是key-value键值对的集合，每一个键也叫一个Entry（桶），这些Entry分散存储在每一个数组中，该数组是HashMap的主干。
2.链表
因为数组Table的长度是有限的，使用hash函数计算时可能会出现index冲突的情况，所以要链表来解决冲突；
数组Table的每一格元素不单纯只是一个Entry对象还有链表的头结点，每一格Entry对象通过Next指针指向下一个Entry节点；
当新来的Entry映射到冲突数组位置时，只需要插入对应的链表位置即可（一般采用头插法）。
3.红黑二叉树
当链表长度超过阈值（8）会将链表转化为红黑树，用于提高性能
关于红黑树相关知识，点击链直达《什么是红黑树》
关于为什么数组中的一个桶里，需要存储为链表，则需要了解hash冲突。简单来说就是往hashMap里新增key，value的时候，如果新添加的key的hashCode与之前某个key存储的hashCode相同，则产生了hash冲突，hashMap采用链地址法解决冲突。将所有哈希地址相同的都链接在同一个链表中 ，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
关于hash冲突的初步理解，点击链直达《关于hash冲突的初步理解》
举个例子，可以让读者更容易理解:
比如调用 hashMap.put("China", 0) ，插入一个Key为“China"的元素；这时候我们需要利用一个哈希函数来确定Entry的具体插入位置(index)。
（1）通过index = Hash("China")，假定最后计算出的index是2，那么Entry的插入结果如下：
（2）但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样：
（3）经过hash函数计算发现即将插入的Entry的index值也为2，这样就会与之前插入的Key为“China”的Entry起冲突；这时就可以用链表来解决冲突。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可；此外，新来的Entry节点插入链表时使用的是“头插法”，即会插在链表的头部，因为HashMap的发明者认为后插入的Entry被查找的概率更大。
本人在阅读其他技术文章时，发现有人提到为什么链表的长度为8是变成红黑树？为什么为6时又变成链表?，对此进行了深究，得到如下结论：
大部分的文章都是分析链表是怎么转换成红黑树的，但是并没有说明为什么当链表长度为8的时候才做转换动作，初略的猜测是因为时间和空间的权衡。
当链表长度为6时，链表查询的平均长度为：6/2=3
红黑树查询的平均长度为：log(6)=2.6
当链表长度为8时，链表查询的平均长度为：8/2=4
红黑树查询的平均长度为：log(8)=3
根据两者的函数图也可以知道随着bin中的数量越多那么红黑树花的时间远远比链表少，所以我觉得这也是原因之一。为7的时候两者应该是 链表花的时间小于红黑树的，但是为什么不是在7的时候转成链表呢，我觉得可能是因为把7当做一个链表和红黑树的过渡点。
事实上真的是因为考虑到时间复杂度所以才把是在8的时候进行转成红黑树吗？其实这并不是真正的原因
至于为什么阈值是8，我想，去源码中找寻答案应该是最可靠的途径，在源码第145-197行记录了相关说明（JDK8）。
* This map usually acts as a binned (bucketed) hash table, but
* when bins get too large, they are transformed into bins of
* TreeNodes, each structured similarly to those in
* java.util.TreeMap. Most methods try to use normal bins, but
* relay to TreeNode methods when applicable (simply by checking
* instanceof a node). Bins of TreeNodes may be traversed and
* used like any others, but additionally support faster lookup
* when overpopulated. However, since the vast majority of bins in
* normal use are not overpopulated, checking for existence of
* tree bins may be delayed in the course of table methods.
*
* Tree bins (i.e., bins whose elements are all TreeNodes) are
* ordered primarily by hashCode, but in the case of ties, if two
* elements are of the same "class C implements Comparable<C>",
* type then their compareTo method is used for ordering. (We
* conservatively check generic types via reflection to validate
* this -- see method comparableClassFor). The added complexity
* of tree bins is worthwhile in providing worst-case O(log n)
* operations when keys either have distinct hashes or are
* orderable, Thus, performance degrades gracefully under
* accidental or malicious usages in which hashCode() methods
* return values that are poorly distributed, as well as those in
* which many keys share a hashCode, so long as they are also
* Comparable. (If neither of these apply, we may waste about a
* factor of two in time and space compared to taking no
* precautions. But the only known cases stem from poor user
* programming practices that are already so slow that this makes
* little difference.)
*
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million这段内容说到：
TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。
这样就解析了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，说白了就是trade-off，空间和时间的权衡。
当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布（如何通俗理解泊松分布？），我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。
通俗点将就是put进去的key进行计算hashCode时 只要选择计算hash值的算法足够好(hash碰撞率极低)，从而遵循泊松分布，使得桶中挂载的bin的数量等于8的概率非常小，从而转换为红黑树的概率也小，反之则概率大。
所以，之所以选择8，不是拍脑袋决定的，而是根据概率统计决定的。由此可见，发展30年的Java每一项改动和优化都是非常严谨和科学的！！！
源码解析
属性
/*** 默认的初始容量为16*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;/*** 最大的容量为2的30次方*/
static final int MAXIMUM_CAPACITY = 1 << 30;/*** 默认的装载因子*/
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;/*** 数组*/
transient Node<K,V>[] table;/*** 作为entrySet()的缓存*/
transient Set<Map.Entry<K,V>> entrySet;/*** 元素的数量*/
transient int size;/*** 修改次数，用于在迭代的时候执行快速失败策略*/
transient int modCount;/*** 当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor*/
int threshold;/*** 装载因子*/
final float loadFactor;
（1）容量
容量为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化。
（2）装载因子
装载因子用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
（3）树化
树化，当容量达到64且链表的长度达到8时进行树化，当链表的长度小于6时反树化。
Node内部类
Node是一个典型的单链表节点，其中，hash用来存储key计算得来的hash值。
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;
}
TreeNode内部类
这是一个神奇的类，它继承自LinkedHashMap中的Entry类，关于LInkedHashMap.Entry这个类我们后面再讲。
TreeNode是一个典型的树型节点，其中，prev是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。
// 位于HashMap中
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;
}// 位于LinkedHashMap中，典型的双向链表节点
static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}
}
HashMap()构造方法
空参构造方法，全部使用默认值。
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap(int initialCapacity)构造方法
调用HashMap(int initialCapacity, float loadFactor)构造方法，传入默认装载因子。
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
HashMap(int initialCapacity, float loadFactor)构造方法
判断传入的初始容量和装载因子是否合法，并计算扩容门槛，扩容门槛为传入的初始容量往上取最近的2的n次方。
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);
}static final int tableSizeFor(int cap) {// 扩容门槛为传入的初始容量往上取最近的2的n次方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;
}
put(K key, V value)方法
添加元素的入口。
public V put(K key, V value) {// 调用hash(key)计算出key的hash值return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;// 如果key为null，则hash值为0，否则调用key的hashCode()方法// 并让高16位与整个hash异或，这样做是为了使计算出的hash更分散return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}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 = (tab = resize()).length;// (n - 1) & hash 计算元素在哪个桶中// 如果这个桶中还没有元素，则把这个元素放在桶中的第一个位置if ((p = tab[i = (n - 1) & hash]) == null)// 新建一个节点放在桶中tab[i] = newNode(hash, key, value, null);else {// 如果桶中已经有元素存在了Node<K, V> e;K k;// 如果桶中第一个元素的hash与待插入元素的hash相同，或者key相同，保存到e中用于后续修改value值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)// 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);else {// 如果桶中第一个元素的hash与待插入元素的hash相同，但是key不相同的情况// 遍历这个桶对应的链表，binCount用于存储链表中元素的个数for (int binCount = 0; ; ++binCount) {// 如果当前节点无下级节点（即最后一个节点），则在链表最后插入一个新节点if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 如果插入新节点后链表长度大于8，则判断是否需要树化，因为第一个元素没有加到binCount中，所以这里-1if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果待插入的key在链表中找到了，则退出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//将当前节点指向下级节点p = e;}}// 如果找到了对应key的元素if (e != null) { // existing mapping for key// 记录下旧值V oldValue = e.value;// 判断是否需要替换旧值if (!onlyIfAbsent || oldValue == null)// 替换旧值为新值e.value = value;// 在节点被访问后做点什么事，在LinkedHashMap中用到afterNodeAccess(e);// 返回旧值return oldValue;}}// 到这里了说明没有找到元素// 修改次数加1++modCount;// 元素数量加1，判断是否需要扩容if (++size > threshold)// 扩容resize();// 在节点插入后做点什么事，在LinkedHashMap中用到afterNodeInsertion(evict);// 没找到元素返回nullreturn null;
}
（1）计算key的hash值；
（2）如果桶（数组）数量为0，则初始化桶；
（3）如果key所在的桶没有元素，则直接插入；
（4）如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理；
（5）如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点；
（6）如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中；
（7）如果找到了对应key的元素，则转后续流程（9）处理；
（8）如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化；
（9）如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值；
（10）如果插入了元素，则数量加1并判断是否需要扩容；
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;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {// 如果旧容量达到了最大容量，则不再进行扩容threshold = Integer.MAX_VALUE;return oldTab;} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两倍，扩容门槛也扩大为两倍newThr = oldThr << 1; // double threshold} else if (oldThr > 0) // initial capacity was placed in threshold// 使用非默认构造方法创建的map，第一次插入元素会走到这里// 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛newCap = oldThr;else { // zero initial threshold signifies using defaults// 调用默认构造方法创建的map，第一次插入元素会走到这里// 如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {// 如果新扩容门槛为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;// 如果桶中第一个元素不为空，赋值给eif ((e = oldTab[j]) != 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// 如果这个链表不止一个元素且不是一颗树// 则分化成两个链表插入到新的桶中去// 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中// 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去// 也就是分化成了两个链表Node<K, V> loHead = null, loTail = null;Node<K, V> hiHead = null, hiTail = null;Node<K, V> next;do {next = e.next;// (e.hash & oldCap) == 0的元素放在低位链表中// 比如，3 & 4 == 0if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;} else {// (e.hash & oldCap) != 0的元素放在高位链表中// 比如，7 & 4 != 0if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 遍历完成分化成两个链表了// 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}
（1）如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12；
（2）如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方；
（3）如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍；
（4）创建一个新容量的桶；
（5）搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置；
可以看到，resize()方法对整个数组以及桶进行了遍历，极其耗费性能，所以再次强调在我们明确知道map要用的容量的时候，使用指定初始化容量的构造函数。
在resize前和resize后的元素布局如下：
再次强调一下，拆分后的结果不一定是均分，要看你存的值
TreeNode.putTreeVal(...)方法
插入元素到红黑树中的方法。
final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab,int h, K k, V v) {Class<?> kc = null;// 标记是否找到这个key的节点boolean searched = false;// 找到树的根节点TreeNode<K, V> root = (parent != null) ? root() : this;// 从树的根节点开始遍历for (TreeNode<K, V> p = root; ; ) {// dir=direction，标记是在左边还是右边// ph=p.hash，当前节点的hash值int dir, ph;// pk=p.key，当前节点的key值K pk;if ((ph = p.hash) > h) {// 当前节点的hash比待插入的hash大，说明待插入的节点在当前节点左边dir = -1;}else if (ph < h)// 当前节点的hash比待插入的hash小，说明待插入的节点在当前节点右边dir = 1;else if ((pk = p.key) == k || (k != null && k.equals(pk)))// 两者hash相同且key相等，说明找到了节点，直接返回该节点// 回到putVal()中判断是否需要修改其value值return p;else if ((kc == null &&// 如果k是Comparable的子类则返回其真实的类，否则返回null(kc = comparableClassFor(k)) == null) ||// 如果k和pk不是同样的类型则返回0，否则返回两者比较的结果(dir = compareComparables(kc, k, pk)) == 0) {// 这个条件表示两者hash相同但是其中一个不是Comparable类型或者两者类型不同// 比如key是Object类型，这时可以传String也可以传Integer，两者hash值可能相同// 在红黑树中把同样hash值的元素存储在同一颗子树，这里相当于找到了这颗子树的顶点// 从这个顶点分别遍历其左右子树去寻找有没有跟待插入的key相同的元素if (!searched) {TreeNode<K, V> q, ch;searched = true;// 遍历左右子树找到了直接返回if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null))return q;}// 如果两者类型相同，再根据它们的内存地址计算hash值进行比较dir = tieBreakOrder(k, pk);}TreeNode<K, V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {// 如果最后确实没找到对应key的元素，则新建一个节点Node<K, V> xpn = xp.next;TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);if (dir <= 0)xp.left = x;elsexp.right = x;xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K, V>) xpn).prev = x;// 插入树节点后平衡// 把root节点移动到链表的第一个节点moveRootToFront(tab, balanceInsertion(root, x));return null;}}
}
（1）寻找根节点；
（2）从根节点开始查找；
（3）比较hash值及key值，如果都相同，直接返回，在putVal()方法中决定是否要替换value值；
（4）根据hash值及key值确定在树的左子树还是右子树查找，找到了直接返回；
（5）如果最后没有找到则在树的相应位置插入元素，并做平衡；
treeifyBin()方法
如果插入元素后链表的长度大于等于8则判断是否需要树化。
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)// 如果桶数量小于64，直接扩容而不用树化// 因为扩容之后，链表会分化成两个链表，达到减少元素的作用// 当然也不一定，比如容量为4，里面存的全是除以4余数等于3的元素// 这样即使扩容也无法减少链表的长度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);}
}
TreeNode.treeify()方法
真正树化的方法。
final void treeify(Node<K, V>[] tab) {TreeNode<K, V> root = null;for (TreeNode<K, V> x = this, next; x != null; x = next) {next = (TreeNode<K, V>) x.next;x.left = x.right = null;// 第一个元素作为根节点且为黑节点，其它元素依次插入到树中再做平衡if (root == null) {x.parent = null;x.red = false;root = x;} else {K k = x.key;int h = x.hash;Class<?> kc = null;// 从根节点查找元素插入的位置for (TreeNode<K, V> p = root; ; ) {int dir, ph;K pk = p.key;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)dir = tieBreakOrder(k, pk);// 如果最后没找到元素，则插入TreeNode<K, V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;// 插入后平衡，默认插入的是红节点，在balanceInsertion()方法里root = balanceInsertion(root, x);break;}}}}// 把根节点移动到链表的头节点，因为经过平衡之后原来的第一个元素不一定是根节点了moveRootToFront(tab, root);
}
（1）从链表的第一个元素开始遍历；
（2）将第一个元素作为根节点；
（3）其它元素依次插入到红黑树中，再做平衡；
（4）将根节点移到链表第一元素的位置（因为平衡的时候根节点会改变）；
get(Object key)方法
public V get(Object key) {Node<K, V> e;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;// 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空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;
}
（1）计算key的hash值；
（2）找到key所在的桶及其第一个元素；
（3）如果第一个元素的key等于待查找的key，直接返回；
（4）如果第一个元素是树节点就按树的方式来查找，否则按链表方式查找；
TreeNode.getTreeNode(int h, Object k)方法
final TreeNode<K, V> getTreeNode(int h, Object k) {// 从树的根节点开始查找return ((parent != null) ? root() : this).find(h, k, null);
}final TreeNode<K, V> find(int h, Object k, Class<?> kc) {TreeNode<K, V> p = this;do {int ph, dir;K pk;TreeNode<K, V> pl = p.left, pr = p.right, q;if ((ph = p.hash) > h)// 左子树p = pl;else if (ph < h)// 右子树p = pr;else if ((pk = p.key) == k || (k != null && k.equals(pk)))// 找到了直接返回return p;else if (pl == null)// hash相同但key不同，左子树为空查右子树p = pr;else if (pr == null)// 右子树为空查左子树p = pl;else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)// 通过compare方法比较key值的大小决定使用左子树还是右子树p = (dir < 0) ? pl : pr;else if ((q = pr.find(h, k, kc)) != null)// 如果以上条件都不通过，则尝试在右子树查找return q;else// 都没找到就在左子树查找p = pl;} while (p != null);return null;
}
经典二叉查找树的查找过程，先根据hash值比较，再根据key值比较决定是查左子树还是右子树。
remove(Object key)方法
public V remove(Object key) {Node<K, V> e;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;// 如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空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;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 如果第一个元素正好就是要找的元素，赋值给node变量后续删除使用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);}}// 如果找到了元素，则看参数是否需要匹配value值，如果不需要匹配直接删除，如果需要匹配则看value值是否与传入的value相等if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)// 如果是树节点，调用树的删除方法（以node调用的，是删除自己）((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);else if (node == p)// 如果待删除的元素是第一个元素，则把第二个元素移到第一的位置tab[index] = node.next;else// 否则删除node节点p.next = node.next;++modCount;--size;// 删除节点后置处理afterNodeRemoval(node);return node;}}return null;
}
（1）先查找元素所在的节点；
（2）如果找到的节点是树节点，则按树的移除节点处理；
（3）如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置；
（4）否则按链表删除节点处理；
（5）修改size，调用移除节点后置处理等；
TreeNode.removeTreeNode(...)方法
final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,boolean movable) {int n;// 如果桶的数量为0直接返回if (tab == null || (n = tab.length) == 0)return;// 节点在桶中的索引int index = (n - 1) & hash;// 第一个节点，根节点，根左子节点TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;// 后继节点，前置节点TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;if (pred == null)// 如果前置节点为空，说明当前节点是根节点，则把后继节点赋值到第一个节点的位置，相当于删除了当前节点tab[index] = first = succ;else// 否则把前置节点的下个节点设置为当前节点的后继节点，相当于删除了当前节点pred.next = succ;// 如果后继节点不为空，则让后继节点的前置节点指向当前节点的前置节点，相当于删除了当前节点if (succ != null)succ.prev = pred;// 如果第一个节点为空，说明没有后继节点了，直接返回if (first == null)return;// 如果根节点的父节点不为空，则重新查找父节点if (root.parent != null)root = root.root();// 如果根节点为空，则需要反树化（将树转化为链表）// 如果需要移动节点且树的高度比较小，则需要反树化if (root == null|| (movable&& (root.right == null|| (rl = root.left) == null|| rl.left == null))) {tab[index] = first.untreeify(map); // too smallreturn;}// 分割线，以上都是删除链表中的节点，下面才是直接删除红黑树的节点（因为TreeNode本身即是链表节点又是树节点）// 删除红黑树节点的大致过程是寻找右子树中最小的节点放到删除节点的位置，然后做平衡，此处不过多注释TreeNode<K, V> p = this, pl = left, pr = right, replacement;if (pl != null && pr != null) {TreeNode<K, V> s = pr, sl;while ((sl = s.left) != null) // find successors = sl;boolean c = s.red;s.red = p.red;p.red = c; // swap colorsTreeNode<K, V> sr = s.right;TreeNode<K, V> pp = p.parent;if (s == pr) { // p was s's direct parentp.parent = s;s.right = p;} else {TreeNode<K, V> sp = s.parent;if ((p.parent = sp) != null) {if (s == sp.left)sp.left = p;elsesp.right = p;}if ((s.right = pr) != null)pr.parent = s;}p.left = null;if ((p.right = sr) != null)sr.parent = p;if ((s.left = pl) != null)pl.parent = s;if ((s.parent = pp) == null)root = s;else if (p == pp.left)pp.left = s;elsepp.right = s;if (sr != null)replacement = sr;elsereplacement = p;} else if (pl != null)replacement = pl;else if (pr != null)replacement = pr;elsereplacement = p;if (replacement != p) {TreeNode<K, V> pp = replacement.parent = p.parent;if (pp == null)root = replacement;else if (p == pp.left)pp.left = replacement;elsepp.right = replacement;p.left = p.right = p.parent = null;}TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);if (replacement == p) { // detachTreeNode<K, V> pp = p.parent;p.parent = null;if (pp != null) {if (p == pp.left)pp.left = null;else if (p == pp.right)pp.right = null;}}if (movable)moveRootToFront(tab, r);
}
（1）TreeNode本身既是链表节点也是红黑树节点；
（2）先删除链表节点；
（3）再删除红黑树节点并做平衡；
总结
（1）允许key和value为null
（2）HashMap是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构；
（3）map通常情况下都是hash桶结构，但是当桶太大的时候，会转换成红黑树，可以增加在桶太大情况下访问效率，但是大多数情况下，结构都以桶的形式存在，所以检查是否存在树节点会增加访问方法的时间
（4）HashMap的默认初始容量为16（1<<4），默认装载因子为0.75f，容量总是2的n次方；
（5）常来说，默认的填充因为0.75是一个时间和空间消耗的良好平衡。较高的填充因为减少了空间的消耗，但是增加了查找的时间
（6）HashMap扩容时每次容量变为原来的两倍；
（7）最好能够在创建HashMap的时候指定其容量，这样存储效率比使其存储空间不够后自动增长更高。毕竟重新调整耗费性能
（8）当桶的数量小于64时不会进行树化，只会扩容；
（9）当桶的数量大于64且单个桶中元素的数量大于8时，进行树化；
（10）当单个桶中元素数量小于6时，进行反树化；
（11）HashMap是非线程安全的容器；
（12）HashMap查找添加元素的时间复杂度都为O(1)；
（13）访问集合的时间与map的容量和键值对的大小成比例
（14）使用大量具有相同hashcode值的key，将降低hash表的表现，最好能实现key的comparable
参考链接：https://www.cnblogs.com/tong-yuan/p/10638912.html
参考链接：https://www.cnblogs.com/joemsu/p/7724623.html
这篇关于深读源码-java集合之HashMap源码分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
