前言
今天代码也不想写，突然想起了HashMap，以前一直觉得还没到看源码的能力（当然现在也感觉没有），那就硬啃吧。我们就从最经常使用的的几个操作进行HashMap的源码分析，此次的源码分析基于Jdk1.8版本来进行。文章一些相关内容参考了网络上的大佬，如有错误也请多多指教。
正文
HashMap的介绍
1.HashMap是一种根据键（key）值（value）来进行存储的数据结构，而且存储多个值的时候，key是不能相同的，也可以对已经有key的值进行修改并覆盖之前存在的值。
2.HashMap最多只允许一条存储数据的key为null，可允许多个value为null。
3.HashMap是线程不安全的，Hashtable是线程安全的。
HashMap的基本使用
public static void main(String[] args) {
//创建一个HashMap的实例，可以传入泛型，以保存任意的数据类型
HashMap<String, String> map = new HashMap<>();
//插入一个key为1，value为hello进行保存。
map.put("1", "hello");
//查找一个key为1里面的内容，返回值根据泛型。
map.get("1");
//删除一个key为1的值，包括key也进行删除。
map.remove("1");
}
在JDK1.8之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。至于红黑树是什么，以后我会也会专门写一篇文章记录一下。
源码分析之实例化
//实例化构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
这个就是一个很简单点的无参数的构造函数，这也是我们最常用的一种构造函数，它初始化了加载因子为默认的值。
//加载因子的默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
加载因子是表示Hsah表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。
源码分析之put函数分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
进行插入函数的时候会调用putVal这个函数，然后分别传进key和value进行实现，这里注意的是hash这个函数方法，它是计算key合适的hash值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
它通过把key的hashcode的值往右移了16位，即丢弃低16位，高16位全为0 ，然后进行异或运算，这样做的同时可以保证最小的开销，扰动处理次数也从 4次位运算 + 5次异或运算 降低到 1次位运算 + 1次异或运算。
然后是putVal函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
//这里是判断是否第一次添加元素，如果是的话，调用resize方法进行扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //获得扩容后的长度。
// i = (n - 1) & hash 即上边讲得元素存储在 map 中的数组角标计算
//如果对应位置有已经有元素了 且 key 是相同的则覆盖元素
if ((p = tab[i = (n - 1) & hash]) == null) //判断是否hash值产生冲突，如果没有就创建Node赋值
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K,V> e; K k;
//如果p的的位置已经有值了，而且key相同，那就覆盖值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof HashMap.TreeNode)//这里判断如果当前节点已经是红黑树，就变转换成红黑树的节点
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //hash值计算出的索引相同（就是已经有元素了），而且key不同的时候 //循环整个单列表
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;
}
//遍历发现有key的值与要插入的可以相同，替换value，并停止循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//移动指针
p = e;
}
}
//循环完毕后e不等于空，就替换e所指的节点的value
if (e != null) { // existing mapping for key
V oldValue = e.value; //保存原来的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//这个方法在 HashMap 中是空实现，在 LinkedHashMap 中有关系
return oldValue;
}
}
//增加一次操作数
++modCount;
//增加一次后如果size大于扩容阈值，就进行扩容,threshold代表扩容阈值
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
插入方法图表示
1.从这个函数我们可以发现，它是放在一个Node数组里面的，首先判断是否table是否为空，如果是空的话今夕resize扩容，
2.然后进行计算要插入的索引位置，通过i = (n - 1) & hash。
3.接下来判断是否存在key，没有的话就进行插入到数组当中，如果有key，但是要插入的位置发现也有key且值不相同的话，就要进行循环单链表，然后查询是否有相同的节点，如果没有，就在尾部插入新的节点。
4.如果插入的单链表的长度大于阈值，就要转换成红黑树。
5.插入以后，再次判断size有没有超过阈值，如果有则要再次进行扩容。
HashMap的扩容
final HashMap.Node<K,V>[] resize() {
//先指向到旧的tab上
HashMap.Node<K,V>[] oldTab = table;
//旧tab的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的扩容阈值
int oldThr = threshold;
//定义一个新的值
int newCap, newThr = 0;
//判断长度是否大于0，如果是的话扩容2倍，扩容阈值也是原来的2倍
if (oldCap > 0) {
//如果旧的已经到达了2^30，那么就不在扩容，直接返回，并且长度直接为MAXIMUM_CAPACITY
//设置后不能安装新的元素
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//扩容为原来的2倍，阈值也是2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldThr 不为空，代表我们使用带参数的构造方法指定了加载因子并计算了
//初始初始阈值 会将扩容阈值 赋值给初始容量这里不再是期望容量，
//但是 >= 指定的期望容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//如果是空的进行初始化容量，长度和阈值分别是16和12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的阈值是0，就计算新的阈值，对应的是当前 table 为空，但是有阈值的情况
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
//因为扩容是容量翻倍，
//原链表上的每个节点 现在可能存放在原来的下标，即low位，
//或者扩容后的下标，即high位
//低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
//高位链表的头节点、尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//用来存放原链表中的节点
do {
next = e.next;
// 利用哈希值 & 旧的容量，可以得到哈希值去模后，
//是大于等于 oldCap 还是小于 oldCap，
//等于 0 代表小于 oldCap，应该存放在低位，
//否则存放在高位（稍后有图片说明）
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);
//将低位链表存放在原index处，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将高位链表存放在新index处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
return newTab;
}
}
其实就是找到之前的扩容的数组大小，然后进行扩容，一般都是扩容2倍，然后将之前的hash表拷到新的hash表中。
插入的代码还是可以看得懂的，resize方法第一部分理解下都懂，第二部分直接懵逼，通过大佬写的注释，稍微理解了一下。就是扩容的容量的翻倍，所以原来的节点，可能放到了新的位置上，也有可能放到了oldcap的位置上。
HashMap的查找元素方法get
public V get(Object key) {
//创建一个新的node
HashMap.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;
//判断tab是否为空
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);
//如果不是，就代表是单链表，就遍历单链表找到key和value
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
查找方法就相对与简单很多了，通过getNode方法进行查找，其中key的值要进行hash计算，然后进行返回。
在getNode方法里，也会判断查找的位置是红黑树还是单链表，如果是单链表就会调用getTreeNode方法进行查找，不是的就进行循环查找，最后返回要找的值。
HashMap的删除方法remove
public V remove(Object key) {
HashMap.Node<K,V> e;
//matchValue如果这个值为 true 则表示只有当 Value 与第三个参数 Value 相同的时候才删除对一个的节点
//movable 这个参数在红黑树中先删除节点时候使用 true 表示删除并其他数中的节点。
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index;
//判断tab是否为空，长度是否大于0，而且查找位置上有没有对应的元素。
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//这里是创建要删除的node
HashMap.Node<K,V> node = null, e; K k; V v;
//判断首位hash是不是要删除的，如果是就赋值给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 HashMap.TreeNode)
node = ((HashMap.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);
}
}
//node如果不为空，就是代表了找到了要删除的节点
// !matchValue 是否不删除节点
//这里也进行判断要删除的节点的值是否相同
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//删除节点
if (node instanceof HashMap.TreeNode)
((HashMap.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;
}
删除函数看着很长，其实细细品味下来也是很好理解，判断tab为空，然后在判断是否首位是不是要删除的节点，如果不是，就往下接着寻找，然后判断要删除的节点的位置是单链表还是红黑树，然后再以它们的方式去查找，然后在进行删除，注意的是，当我看到最后的时候发现了matchValue 这个变量的时候，而且之前的remvove也有出现过，然后百度了一下发现还有个remove函数。
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
看这个实现就知道了，就是可以一起判断key和value是不是要删除的那个元素（以前我都不知道还有这个rmove方法，无奈-_-||）。
总结
HashMap这里只是记录了最常用的几个操作，因为能力和实践有限，还有一大部分的源代码没有去阅读，而且分析的过程，发现能写出这些的都是大佬中的大佬，此篇文章也参考了一些网络上大佬的分析，经过此次的初探，也对HashMap有个初步的了解。
参考
- [搞懂 Java HashMap 源码] https://www.jianshu.com/p/9ea8dd8dd40c
网友评论