背景
促使自己开始研究源码的原因主要有两个，第一个是在面试高级工程师的时候，源码这块是必问的，第二个原因是现在框架是越来越多，也没有太多精力去学习，于是就准备开始研究各种底层知识，看看那些底层大佬们是如何写代码，这是踏出的第一步，后面会有越来越多的源码学习经验和大家一起分享，希望大家能够提出宝贵的意见。话不多说，直接进入我们今天的主题
开发环境
| 开发工具 | JDK版本 |
|---|---|
| IDEA 2020 | JDK1.8 |
抛砖引玉
首先给大家呈上几道经典的有关hashmap 1.8的面试题？
- HashMap的初始容量为什么是2的幂次方？
- HashMap在什么时候会进行扩容？
- HashMap是如何进行扩容的？
- HashMap底层数据结构？
- HashMap1.8为什么引入红黑树？
- HashMap什么时候会将链表转换成红黑树？
- HashMap在多线程情况下会出现什么？
- 能说说HashMap的hash算法么？
- HashMap是如何定位到key所在数组上的位置的?
先说这么多吧，相信大家应该都会被问过这些问题，会不会很惊讶，就一个hashmap都能整出这么多面试问题？接下来我会通过本篇文章带着大家一起解读hashmap的这些骚操作，大家看完之后，上面的这些面试题都会知道该如何解答了，我们开始吧~
在讲代码之前我想先和大家说下hashmap里面的一个数据结构
- 首先hashmap底层是一个数据结构，为什么要用数组呢，因为他查找非常的快，于是刚开始他长这样,他的初始长度是16
- 然后我插入一个key，他是怎么计算到自己的位置的呢，通过计算他的hash码，得到一个整数，然后和16取模，就能够将数据散列到0-15的位置了啊，但是jdk会用一个更加牛逼的方法去算出这个位置，后面我会说到的，看完之后，你会觉得算法真香。
- 当有越来越多的数据存进来之后，发现我的那个位置被人占用了，那可咋办呢，我又不能覆盖它吧，然后就有了链表这个新的成员加入，先看下链表和数组的结合
- 也就是说当位置相同的时候，所有的数据都会以链表的形式在那个位置一直往下接，就形成了上面这样的形式
- 加入链表之后，我们的数据存储问题是解决了，但是当这个链表越来越长的时候，我们找起来就费劲了，我们知道链表结构增加和删除是很快的，但是查找的复杂度就是o(n)了，得挨个遍历。所以有必要引入新的成员了，红黑树
- 红黑树是平衡二叉树的一种实现方式，数据结构这块后续会有相关的文章进行讲解，那我们就来看下引入红黑树之后，是怎样一个组合呢
好的，hashmap结构这块我已经和大家大概的讲完了，下面就让我们一步一步分析代码，来解决我们心中的疑惑吧！
代码示例
一个简单地main方法，然后跟着这个方法，我们调到map的世界里面去
public class Main {
public static void main(String[] args) {
// write your code here
Map<String,String> map = new HashMap<>(27);
map.put("name","乐哉开讲");
}
}我们先进入到new HashMap，看看构造器都给我们做了什么
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}可以看到他又调用了另外一个构造方法，并且又调用了另外一个构造方法
DEFAULT_LOAD_FACTOR 这个就是一个负载因子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);
}我们来分下这段代码，
- 判断我们设置的初始容量是否合法
- 判断初始容量是否大于最大容量 MAXIMUM_CAPACITY = 1 << 30;一般都不会大于这个最大值得，如果大于，就用这个最大值作为初始容量
- 判断负载因子是否合法，后面讲扩容得地方的时候再说这个负载因子是用来干嘛的
- tableSizeFor 是为了计算出 大于等于这个初始容量的最小二次幂，如 15 的最小二次幂为16 7的最小二次幂是8，看下具体是如何实现的，有兴趣的话可以跑下这段代码，看看是不是这样的，所以最终map的初始容量都是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;
}构造器分析完之后，我们在来到开始的地方，执行put方法，我们点进去看下，这里面是我们这次讲的核心的地方，大家认真看下
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}我们看到put方法是去调用putVal方法去执行put逻辑的，先不跟进去看，我们会看到，这里会将key做一个hash运算，看看上面的面试题8，是不是也说到这个了，我们就点进去看下，这个hash他做了什么？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}大家会不会很失望，这里面只有三行代码，能做什么呢？虽然只有只有三行代码，但是这里减小了hash碰撞的机会，什么叫hash碰撞呢，就是我们刚开始的时候提到的有些数据得到了相同的下标，然后会以链表的形式存储，会导致链表过长，这里就是为了让hash的更加均匀，而采取的一些手段，我们来分析下代码
- key如果为空的话，直接返回hash为0
- key进行hashcode的话，会得到一串整数，
- 我们知道整形是占用四个字节，占用32个bit，我们将前16个作为高位，后16个作为低位，然后将32个bit右移16，是不是就能得到高16位的值，然后再讲高位和低位进行疑惑，得到一个新的二进制，为什么这么做呢，因为这样能够在计算元素下标的时候，能够让hash的高位和低位都能参与进行来，减少碰撞的概率
- 返回新的hashcode
hashcode计算完之后，我们再回到上一个方法putVal
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)
n = (tab = resize()).length;
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 {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}数组初始化
这个方法是很长的，大家需要认真的慢慢的看完，我们从第一行开始进行解析
- 首先定义一个Node节点，和一个Node数组
- 接着判断table是否为空或者数组长度是否为0 ，这个table是什么呢，这个table就是存放你创建过得Node数组，如果你第一次put操作的话，这个就是空的，第二次进来就是有内容的
7.假如我们是第一次进来，他会给我们进行resize操作，也就是初始化一个长度的Node数组，我们点进去看下，他都做了什么？顺便说下，当数组进行扩容的时候也会进入到这个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)
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);
}
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
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;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}这个代码写的真长。。。，不过没关系，我们今天就是来一探究竟的，我们一步一步往下看
- 首先把resize之前的Node数组复制给oldTab,保存旧的数组长度和旧的阈值(负载因子*数组长度)
- 接着判断旧的数组容量是否是大于0（扩容的话会进入这个判断条件），如果是大于0的话就判断是否大于最大的容量MAXIMUM_CAPACITY，如果大于的话，会给阈值赋值为这个最大容量，返回oldtab，如果旧数组的容量没有超过这个最大容量，则进行两倍扩容，阈值也会进行扩容
- 如果旧的阈值大于0，则将旧的阈值作为新的数组的大小，这一步我理解的是第一次构造map的时候不是设置了一个初始容量，然后转换为了一个二次幂，这里就是用那个值来初始化一个Node数组
10.如果旧的阈值等于0的话，那就会使用map默认的初始容量16和负载因子0.75来计算数组的容量和阈值大小，
- 为什么最后又要判断下newThr == 0呢，因为这个如果为的话，肯定是第一次初始化数组的时候，他这个阈值是没有计算的，所以需要重新计算下。
- 到目前为止，新的数组已经扩展或初始化好了
- 再次判断if (oldTab != null) ，如果旧的数组不为空的话，说明就是扩容，如果为空则可以直接返回这个数组了，不为空的话，则需要进行扩容后的数据迁移的工作了
数据迁移 - 遍历所有旧数组中的元素
- 判断当前元素是否为空，不为空才进行数据迁移
- 接下来会有三个判断，作用分别为 判断是否是单个节点，判断是否是红黑树节点，判断是否是链表
-
首先判断如果是单个节点，则 通过e的hash值和新的容量-1进行与运算，会得到这个元素在新数组中的索引位置，还记得我们前面说过 jdk用了一个比较厉害的定位元素位置的方法么，这里就是他的实现过程
假如我们有一个数值，我们想让他在0-15中间进行散列，我们想到使用模运算 %16,这里给大家介绍另外一种方法，假如是 19 ，16取模之后，会是3，如果将19& （16-1）,计算之后也是3后者效率会更高的，所以jdk采用后面这种方法，更加高效。大家会不会跟困惑这是为啥呢，我在这位大家简单地介绍下：
首先我们知道，与运算的话必须是全部为1则为1，如果要达到这样的效果的话，这个数值必须是2的n次方-1，肯定是所有bit为都为1，这也就是为什么map要求数组容量必须是2的幂次方了。 接下来我们拿到1111这样的数值之后和我们的hash进行运算 11111000110011 & 1111 这样运算之后得到的是3111111111111111 & 1111 这样运算之后得到的是15 永远也不会超过15，大家这下应该知道这个原> 理了吧
- 再接着判断如果是红黑树的话，则进行红黑树的相关操作
- 最后再判断如果是链表的话，则进行遍历迁移
- 这里一个主要的操作是 给索引相同的元素进行均分
- 将元素的hash和老的数组长度进行与操作，如果为，说明他的高位为1，与新的数组长度进行与之后，还是原来的结果，如果不为0，则可以直接将索引下标加上旧的数组长度，然后将节点引到新的数组对应的索引下面，这里大家有可能很懵，说这么多到底是什么意思呢，我以画图的形式和大家说下吧
我们看到上面会有两个table，分别是扩容前的数组和扩容后的数组
- oldTab 数组上的第七个索引上，元素的hash分别为7和15，7 & （8-1）和 15 & (8-1) 都得到的是
7，所以存放到了7上面， - 现在进行扩容，数组长度扩大为16，这时候如果直接拿两个hash值和新的数组长度进行与运算的话，会得到7和15两个位置，这样链表就会被这两个位置均分掉
- 但是我们看代码，jdk并没有这么做，他先判断hash和原先的数组长度进行与操作，之前一直是和数组长度减1做与操作，如果结果为0，说明他在新的数组上面索引的位置还是和当前一样，则直接把数据放到新数组上，如果不为0 ，则只需要把当前索引位置加上旧的数组长度即可，因为数组扩容长旧数组两倍的，
讲了这么多，数组初始化这块讲完了
我们再回到前面的代码
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)
n = (tab = resize()).length;
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 {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}第一个判断处理完之后，我们继续往下看，
- p = tab[i = (n - 1) & hash]) == null 判断如果数组所在的索引位置上的数据如果为空，则直接new一个新的Node直接放在元素上即可
- 如果不为空，则继续往下走
- 如果当前节点不为空，并且它的key值和我们传入的key是相等的，则直接取出这个节点，直接在这个节点上进行操作，后面再说
- 如果节点是红黑树节点，则进行红黑树相关的操作
- 如果上面条件都不满足的，则说明是一个链表结构，
- 遍历链表里面的元素
- 如果在链表里面找到了key值相同的节点，则直接取出这个节点，不再遍历
- 如果已经遍历到链表的最后一个节点都还没有拿到的话，则需要创建新的节点
- 这里有两种情况，通过binCount进行判断，这个变量用来干嘛的呢，我们会看到我们每次进行链表节点的时候都会把这个进行自增，其实也就是记录这个链表的长度
- 如果比较发现 链表的长度已经大于 map中定义的TREEIFY_THRESHOLD - 1的话，也就是7，就会将链表转换为红黑树，将数据存到红黑树中，这里为什么要减掉1呢，其实这块也是面试官必问的，也就是我刚开始提到的一个面试题：什么时候链表会转换成红黑树？map里面定义的是8，这里减了1.是因为在我们进行遍历链表之前，我们已经取出来了数组上面的第一个链表元素了，后面的遍历是基于这个元素的next进行遍历的，所以这里就需要将TREEIFY_THRESHOLD -1作为转换条件判断。
- 最后我们看下这段代码
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}这个e也就是我们上面取出来的元素，如果判断不为空的话，则说明map中已经存在了这个元素，则只需要给他赋上新的值就好了，然后将旧值返回回去，
最后将数组长度加一，如果是更新操作，则不会走到这一步，加一之后如果发现当前的数组中元素的长度如果大于阈值则进行扩容操作。
到这里终于把map中最重要的put操作讲完了，get和remove操作大家可以按照这个思路自己去看下咯，刚开始的面试题也在文章里都有讲解到，还有一个多线程情况下，map会出现什么问题，这个后续再说了，本文篇幅有点长。。。，文中有讲的不准确的地方，希望各位大佬指正