一、概述
在Java开发中，HashMap使用的频率还是比较多的，主要通过key-value的形式来存储数据，但是HashMap的原理是怎样的呢？他是如何进行增删改查的呢？所以今天我们就带着这些问题来看源码，主要看它的put，get，remove方法。本文我们使用的JDK版本为1.8。
二、源码分析
在分析源码之前，我们先来看一下HashMap的简单使用：
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("key","张三");
System.out.println(hashMap.get("key"));
}
我们按照这个顺序来继续分析源码，首先来看一下四个构造方法：相关解释已经写在了注释中。
构造一个空的HashMap，默认的初始容量为：16，默认的加载因子为：0.75。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
构造一个空的 指定容量的HashMap，默认的加载因子为：0.75。
public HashMap(int initialCapacity) {
//继续调用了第三个调用方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造一个空的HashMap，指定初始容量，和 加载因子。
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);
}
构造一个与指定Map相同映射的HashMap 可以理解为将Map转为HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
二、增和改
现在我们带着第一个问题：HashMap是如何插入数据的呢？我们直接来看put方法：
@param key 键
@param value 值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看到HashMap的put方法又调用了putVal方法，第一个参数中又调用了hash(key)，我们先来看看hash(key的作用)：这里问题，为什么进行位运算
static final int hash(Object key) {
int h;
//如果key为空，返回0，否则返回key.hashCode的异或运算 位移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里简单举例一个异或运算：比如
h=2987074，在位运算中都是通过二进制进行，
h的二进制：0010 1101 1001 0100 0100 0010
h位移16位之后的二进制：0000 0000 0000 0000 0010 1101
这两个二进制数再进行^（异或）运算，
结果为：0010 1101 1001 0100 0110 1111，转为十进制为：2987119。
看完hash方法之后继续看putVal方法，但是在看putVal方法之前，我们先了解一下HashMap的一个内部类，Node。
在Node类中，存储了hash，key,value,和next，next就是当前node指向的下一个节点，这就是一个链表结构。
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;
}
}
继续来看putVal方法：
/**
* @param hash key 的hash
* @param key
* @param value
* @param onlyIfAbsent 如果为true，则不更改现有值
* @param evict 如果为false，则表处于创建模式
* @return valur or null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//如果table为空，或 长度为0时
//这里的table为Node<K,V>[] table，是一个数组，Node相当于链表，所以到这里我们可以知道HashMap
//底层使用的是数组+链表
if ((tab = table) == null || (n = tab.length) == 0)
//n = 创建一个新的tab并返回长度
//这里的n就是tab的长度，即Node<K,V>[]数组长度
n = (tab = resize()).length;
//通过数组长度-1 与 hasn进行与运算拿到i即下标，再通过下标取数组中的node，
//如果为null是，创建一个新的node，赋值给tab[i]
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
//如果p中和传入的hash相等，与 key相等时，
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将p即node，赋值给e
e = p;
//否则 p是一个树节点，将其插入到树中，并赋值给e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//如果p的下一个节点为空，则创建一个node，赋值给p.next，
//这里采用的是尾插法，
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果数量大于 TREEIFY_THRESHOLD 即8时，将链表Node，转换为树（红黑树）
//到这里 HashMap的结构就成为了数组+链表+红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果hash相等，则直接跳出循环，
//到这里就表示当前的e（node）和传入的值已经相等了，所以没必要循环了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果node不为空，保存value为oldValue，
if (e != null) { // existing mapping for key
V oldValue = e.value;
//如果需要改变现有值，value为空时，将传入的value赋值给node.value
//这里对应的就是修改key的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果当前长度大于默认长度
//++size 就是每次put后size+1，getSize()就是这个size
if (++size > threshold)
//执行扩容
resize();
afterNodeInsertion(evict);
return null;
}
三、查
put方法已经分析完成了，相关的注释我已经写在了上面，大家可以认真看，其实并不太难，接下来我们来看下一个问题，HashMap中是如何通过key获取Value的呢？接下来继续看get方法：
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;
//如果tab不为null，与 查找到的node不为空时，
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一个node hash 和key和我们想要的hash key相同，直接返回此node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果node的next不为空，
if ((e = first.next) != null) {
//如果node时TreeNode（树节点）
if (first instanceof TreeNode)
//从树中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//通过循环 遍历节点的next，如果找到hash和key相同的则返回。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//没有找到 返回null
return null;
}
四、删
到这里，增改查就已经分析完毕，最后来看删除的方法：remove();
public V remove(Object key) {
Node<K,V> e;
//通过removeNode方法查找对应的Node节点返回node.value
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
在removeNode方法中，和getNode原理大致相同，我们来简单看一下：
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; //n为长度，index为下标
//如果tab不为空 与 查找到的node不为空时，
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中的hash和传入的hash相等，且key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将p赋值给node
node = p;
//如果next不为空时，
else if ((e = p.next) != null) {
//如果p是树节点
if (p instanceof TreeNode)
//node = 从树节点中查找
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//否则 遍历table，知道找到要删除的node
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不为空，与 值相等时
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果node时树节点，就从树节点中删除。
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//更改node的next为要删除的next，就是更改当前node的next引用 为 要删除的next的引用
//这样就相当于与要删除的节点断开了连接 从而实现了删除
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
//size-1
--size;
afterNodeRemoval(node);
//最后返回删除的node
return node;
}
}
return null;
}
到这里HashMap的增删改查的源码我们已经看完了，所对应的为：put()，get()，remove()。在上面的代码中，我都已经写好了注释，根据注释结合代码看还是非常通俗易懂的。
五、总结
通过上面的分析，我们已经基本理解了HashMap增删改查的大致流程了，我们总结如下：
- 增(put)：
①：通过key的hashcode和hashcode的位移16位进行异或运算得到一个hash值。
②：如果存储节点(Node)的数组为空，则创建一个新的数组。
③：通过数组的长度-1 和 上面得到的hash进行&运算，得到一个node即p；
④：如果p为空，说明该位置没有存储节点，则创建一个node对象，并存入对应的下标中。
⑤：否则，p不为空时，判断Node是否是TreeNode(树节点)，如果是则插入到树节点。
⑥：如果不是树节点，则遍历链表，直到链表的next为空时，将此node赋值给next。
⑦：同时判断遍历的次数，如果大于等于TREEIFY_THRESHOLD即8-1时，将链表转换为红黑树。
⑧：如果key hash相同，且需要修改value时，则修改value。
⑨：最后进行收尾工作，++size，如果长度大于threshold，进行扩容。
- 改：
其实改的方法是包含在put方法之中的，当传入的key相同时，则根据参数onlyIfAbsent来决定是否更新这个值。
- 查(get)：
①：判断tab不为空时，算出数组中的index，找到头节点node。
②：如果头节点的key和hash与传入的相同，直接返回此node。
③：如果没找到，继续判断，如果node为红黑树结构，则从红黑树中查找。
④：如果没找到，遍历链表，继续查找key hash和传入相同的node，找到则返回。
⑤：没找到，返回null。
- 删(remove)：
查和删的原理大致相同，首先都是通过一系列判断查找出对应的node节点，最后通过更改next的指向来达到删除的效果。其中有一个参数：matchValue，如果为true时，则只会在两个value相等的情况下才会删除。
最后上一张HashMap的结构图，以供大家理解。
HashMap.png
网友评论