HashMap简介
基于哈希表实现，每一个元素key-value存储，内部实现是数据上挂载单链表，容量不足时（超过了阈值，阈值是通过负载因子计算的），会自动扩展（以2倍方式扩容）。
- 允许key value值为null
- 线程不安全
- 实现Serializable，支持序列化
- 实现了Cloneable，支持被克隆
- key-value方式存储
- 自动扩容，根据负载因子计算，为当前容量的2倍
HashMap源码解读
存储数据结构
如下图:（图是copy自网络，无法找到源头，只能先借用啦(^▽^)）
HashMap类结构
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
继承抽象类AbstractMap，实现了序列化Serializable接口，cloneable接口，Map接口
HashMap 重要的常量属性
- 默认桶的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- 默认桶的最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
- 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
- 红黑树转成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
- 由链表转换成红黑树的容量的最小阈值
static final int MIN_TREEIFY_CAPACITY = 64;
- 扩容阈值
int threshold;
构造方法（一共有四种构造方法）
- 默认构造（负载因子为默认大小）
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 指定大小的，指定负载因子的构造方法
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);
}
- 指定大小的构造方法（负载因子为默认）
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- 包含Map的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
单链表的实现
每一个节点是一个Entry对象，每一个node节点都存储有key value，节点的hash值，以及下一个节点的node，实现Map.Entry接口。需要注意到node对象重写了equals方法，当出现hash冲突的时候会通过equals比较是否相同
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;
}
}
计算hashMap容量
计算hashMap容量的大小，也就是桶的大小，说到这，先补充一下知识点
这里我们要知道<<运算符的意义，表示移位操作，每次向左移动一位(相对于二进制来说)，表示乘以2，此处1<<4表示00001中的1向左移动了4位，变成了10000，换算成十进制就是2^4=16，也就是HashMap的默认容量就是16。Java中还有一些位操作符，比如类似的>>(右移)，还有>>>(无符号右移)等，也是需要我们掌握的。这些位操作符的计算速度很快，我们在平时的工作中可以使用它们来提升我们系统的性能。
初始化时，会首先判断初始容量是否小于0，如果小于0，会抛出异常。接着，判断初始容量是否大于最大的容量(即2^31)，如果大于，将初始容量设置为最大初始容量。紧接着，判断加载因子：如果小于等于0，或者不是一个数字，都会抛出异常。等这些校验完成之后，会将HashMap的加载因子和扩容的阈值设置上。这里需要注意一下，threshold(阈值)=capacity*loadFactor。
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;
}
这个方法，是计算桶的大小，根据给定的cap，进行无符号右移，将移动的值与之前的值取非，如下计算逻辑： 例如输入30，求该桶的大小？
int cap = 29
int n = 28 = 29 - 1
第一次 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
右移1位 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
计算结果 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
右移2位 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
计算结果 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
此时看结果已经都是1了，继续移位计算的结果也都是1，所以最终结果是31，如果n>1，则返回31 + 1 = 32，为2的整数次幂。
总结，tableSizeFor方法只是为了让最高位后的值都为1，这样计算出的结果为输入数的最接近2的整数次幂。
求hash值和桶的索引值
接下来重点分析一下求hash值和桶的索引值，这俩个是HashMap最核心的地方，他可以保证哈希表中的元素均匀地散列。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
根据key计算hash值，只计算hash值的几位，使用位操作是计算效率很高。目前不去深究为什么这么设计，我们只要知道，这样设计的目的是为了让hash值分布的更加均匀即可。
求桶的索引值，是key的hash &（tab.length - 1）
有一种方法：除法散列法，用hash值对length取模来计算桶的索引，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低。
hashMap 是使用h&(length-1)的方法代替取模，同样实现了均匀的散列，但效率要高很多。
在上面的tableSizeFor方法，计算出的桶的大小是2的整数次幂，为什么桶的大小一定是2的整数次幂呢？ 首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率； 其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
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;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((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;
}
getNode的2个参数，key的hash值和key，首先判断table是否为null，并且table的length大于0，根据key的hash & table表的长度 - 1，计算到表的索引值，判断在此索引值对应的桶是否存在，如果存在在判断key是否相等或者key的值是否相等。如果找到则返回对应的node，否则继续判断next节点是否存在，并且节点的属性是否为TreeNode，如果为红黑树，则通过树快速查找并返回，否则循环链表，查找key对应的节点。
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
}
put 方法有2个参数，key和value, putVal有四个参数 hash：表示key的hash值 key：待存储的key值 value：待存储的value值，从这个方法可以知道，HashMap底层存储的是key-value的键值对，不只是存储了value onlyIfAbsent：这个参数表示，是否需要替换相同的value值，如果为true，表示不替换已经存在的value evict：如果为false，表示数组是新增模式 我们看到put时所传入的参数put(hash(key), key, value, false, true)，可以得到相应的含义.
- 如果table桶为null，或者大小为0，如果为空，则调用resize()方法，对HashMap进行扩容，这次扩容的结果就是HashMap的初始化一个长度为16的数组。获取到数组的长度n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- hash方法，当key=null时，也是有hash值的，是0，所以，HashMap的key是可以为null的，对比HashTable源码我们可以知道，HashTable的key直接进行了hashCode，如果key为null时，会抛出异常，所以HashTable的key不可以是null
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 接着，根据长度-1和hash值进行按位与运算，算出hash值对应于数组中的位置，如果没有值，则创建一个new node，存储到桶的该索引处
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
- 如果hash冲突，首先判断hash值是否相等，如果不相等，则判断key的值equals是否相等，如果相等，则标记已找到e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
- 如果节点类型为TreeNode，则使用红黑树创建，并标记已找到e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 若3,4未符合，则循环单链表，找到则标记为e
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;
}
- 如果标记e不为null，则表示找到冲突的节点，使用afterNodeAccess更新节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
- modCount 增加1
- 如果桶的++size > threshold，则自动扩展桶的大小，重新分配元素分配
if (++size > threshold)
resize();
- 使用afterNodeInsertion 增加node
下一篇文章将重点分析resize()
参考资料
https://blog.csdn.net/ns_code/article/details/36034955 https://www.jianshu.com/p/7dcff1fd05ad