浅谈HashMap源码
特点：
- 根据对象的
hashCode值存储。 - 非线程安全
- 实现了Serializable接口，支持序列化，实现了Cloneable接口，能被克隆
- jdk1.8 之前，底层由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突。（拉链法）。插入是 头插法
- jdk1.8以后，在解决哈希冲突方面有较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。插入操作是 尾插法
- 访问速度很快
原理：
基于JDK1.8
底层实现
HashMap内部维护了一个存储数据的Entry数组，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过对$n$取模求该key-value对应的存储索引值。当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表。
图中，bucket为哈希数组/桶数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
扩容机制
HashMap内存储数据的Entry数组默认是16，如果没有对Entry扩容机制的话，当存储的数据一多，Entry内部的链表会很长，这就失去了HashMap的存储意义了。所以HasnMap内部有自己的扩容机制。HashMap内部的重要变量：
modCount，修改/删除的总次数Entry，存储对象的实体类，包括Key,Value,hash,nextsize，记录HashMap的底层数组中已用槽（也叫“桶”）的数量。DEFAULT_INITIAL_CAPACITY = 1 << 4，默认初始容量大小是16MAXIMUM_CAPACITY = 1 << 30，最大容量是$2^{30}$threshold，HashMap的阈值，用于判断是否需要调整HashMap的容量- $threshold = 容量capacity*加载因子factor$
DEFAULT_LOAD_FACTOR = 0.75f，默认加载因子为$0.75$- 扩容的条件是：$size > threshold$
扩容是是新建了一个HashMap的底层数组，容量为原来的2倍，把HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。 很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。
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) // 容量×2,阈值×2
newThr = oldThr << 1;
}
else if (oldThr > 0) // 初始化一个有初始容量的table
newCap = oldThr;
else { // 初始化一个空的table
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;
}构造方法
HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中槽的数量（即哈希数组的长度），默认是16。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 扩容操作。
tableSizeFor()函数会处理传入的初始容量，使其为2的整数次幂。
如果指定的容量超过了最大容量MAXIMUM_CAPACITY ，则会初始化为最大容量MAXIMUM_CAPACITY，即$2^{30}$
构造函数源码
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);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* map类型转化为HashMap
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 返回 大于等于cap并且是2的整数次幂的 最小的数
* 运算原理： n的最高位1在第k位，则把[0...k]都变成1，然后+1，即为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;
}
/**
* map类型转化为HashMap
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}关于懒加载问题
new一个HashMap后并不会立刻初始化（如上图源码所示，只标记了属性），而是第一次对HashMap进行put的时候初始化。所以resize()的执行情况有两种，一种是第一次put初始化table，一种是超出了阈值。
加载因子
如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。
hash值
- 先获取到key的hashCode值，
- 然后异或hashCode的高16位 。
因为key的hashCode在大多数情况下都是小于$2^{16}$次方，此时随机性就全部压在了低16位，基于这一点，把hashcode高16位的值通过异或混合到hashCode的低16位，由此来增强hashCode低16位的随机性。
static final int hash(Object key) {
int h;
/**先获取到key的hashCode，然后异或hashCode的高16位.
因为n相对于hashcode的值很小。基于这一点，把hashcode高16位的值通过异或混合到hashCode的低16位，由此来增强hashCode低16位的随机性**/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
获得table索引
hash数组长度为$n$
$hash \% n$
当n是2的幂次方时：$hash \% n$ 等价于： $hash \& (n-1)$
hashmap采用 $hash\&(n-1)$
get()
通过$(n - 1) \& hash$拿到Key对应的链表的索引(头结点)，然后遍历链表/红黑树。
另外需要注意到HashMap的get函数的返回值不能判断一个key是否包含在map中，get返回null有可能是不包含该key；也有可能该key对应的value为null。HashMap中允许key为null，允许value为null。
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;
}put()
先检查table是否初始化，没有的话执行resize()。
根据hash值得出在table中的索引，如果索引上没东西，为空，就把节点放上面。否则，获取链表头结点，比对，如果不是头结点，遍历链表或者红黑树，如果有相同的key，则执行覆盖，如果遍历完了还是没有，那就new一个然后插入。
最后，每次加入键值对后，都要判断当前是否需要扩容$size > threshold ?$，如果成立则进行扩容。
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) // 检查table是否初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 索引i上为空，就new一个放上面
tab[i] = newNode(hash, key, value, null);
else { // 索引i上不为空，就把Key插入到链表后面
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); // 链表长度>=8，这时要么进行扩容操作，要么把链表结构转为红黑树结构
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 已存在相同的Key，覆盖
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 第一次插入Key的话会执行到这里，
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}containsKV()
containsKey(Key)方法和containsValue(Value)方法。前者搜索的是Key对应的一个链表，而后者要搜索哈希数组的所有链表。
contains()源码
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}一些问题：
为什么哈希表的容量一定要是2的整数次幂
首先，length为2的整数次幂，$hash\&(n-1)$就相当于对n取模，这样便保证了散列的均匀，同时也提升了效率；
其次，保证了$hash\&(n-1)$的最后一位可能为0，也可能为1，即与运算后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样$hash\&(n-1)$的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。
因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
为什么是线程不安全/线程不同步的
会造成数据不一致问题
当两个线程A、B同时对同一个桶（哈希数组的插槽）进行put写数据时，当A拿到了链表头结点，CPU时间片耗尽，线程B被调度执行，B也拿到了头结点并且完成了插入，此时切回A，A再执行插入就会覆盖B线程的插入记录，B线程插入记录丢失，造成数据不一致。
在jdk1.7中扩容操作的不安全会造成死循环
jdk1.7中扩容操作是头插法，
transfer代码如下：
transfer()源码
// 将HashMap中的全部元素都添加到newTable中 void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; // ********** e = next; } while (e != null); } } } static int indexFor(int h, int length) { return h & (length-1); }
如果有两个线程T1、T2进行扩容操作，有链表$A \rightarrow B$，头插法数据迁移完成后是$B \rightarrow A$，当T1执行第一行$e = A, next = B$时。线程挂起，切到T2，T2完成了数据迁移$B \rightarrow A$，此时线程A继续执行，使e.next = next 即，$A \rightarrow B$，此时闭环链表，死循环。
jdk1.7与jdk1.8区别
1、 JDK1.7：数组+ 单链表，JDK1.8：数组+链表+红黑树
2、 JDK1.7：头插法，JDK1.8：尾插法 扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；
3、 在计算hash值的时候，JDK1.7用了9次扰动处理=4次位运算+5次异或，而JDK1.8只用了2次扰动处理=1次位运算+1次异或。
4、 jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的；
常用方法：
V get();
V put(Key, Value);
V remove(Key);
boolean remove(key, Value);
void clear();
boolean containsKey(Key);
boolean containsValue(Value);
boolean isEmpty();
Set<K> keySet();
oldV replace(Key, Value);
boolean replace(Key, Value, newValue);
int size();
TQL ::aru:crying::
::aru:crying::
哇，不愧是师傅
(☆ω☆) ::aru:smile::