HashMap集合源码分析
在分析HashMap的源码之前还是先去看一下hash函数部分的知识，之前的数据结构课程中也讲过，现在也记不太清楚了。
哈希 哈希函数 哈希表
什么是散列表?
在数组中查找数据的速度可以达到O(1),是因为数组中的数据有它对应的下标。但是查找链表中的数据时间复杂度就相对很高，因为查找链表中的数据需要从头遍历。所以就希望有一种通过关键字不需要比较就可以获得需要记录的存储位置。这就是一种新的存储技术——散列技术。
散列技术是在存储位置和它的关键子之间建立一个确定的对应关系f,使得每个关键字对应一个存储位置f(key)。
对应关系f称为哈希函数或者散列函数。按照这个思想采用散列技术将数据存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。
哈希函数
在设计哈希函数的时候需要解决的一个问题就是解决哈希冲突，也就是有两个关键字key1和key2，但是却有f(key1)!=f(key2),这就是冲突。
散列函数的构造方法
哈希函数中key值的选取有这么几种方式：
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
此方法常用，f(key) = key mod p(p<=m)。若散列表表长为m,通常p为小于或等于表长的最小质数或不包含小于20质因子的合数。
- 随机数法
处理散列冲突的方法
- 开放地址法
开放地址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找的到。
f1(key) = (f(key)+di) mod m (di=1,2,3,4,....,m-1)
- 再散列函数法
- 链地址法
链地址法是最常用的处理哈希冲突的方法。比如当前有12个数，先开辟长度为12的数组，通过H(key) = key mod 12来计算将当前数据作为结点插入到数组下标对应的结点后面。
HashMap源码分析
Map有常用的四种集合：
- HashMap:使用哈希表实现，在keys或values之中都是无序的
- TreeMap:基于红黑树实现，按key排序
- LinkedHashMap:有序的
- HashTable:与HashMap实现方式一样，但HashTable属于同步(synchronized)的
在看HashMap源码之前带着这几个问题去看：
- 什么时候会使用HashMap?它有什么特点？
- HashMap的工作原理？
- get和put的原理？equals()和hashCode()都有什么作用？
- hash的实现？为什么要这样实现？
- 负载因子是干嘛的？如果HashMap的大小超过了负载因子定义的容量，怎么办？
HashMap的定义
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable
HashMap继承于AbstractMap<K,V>抽象类，实现了Map<K,V>,Cloneable,Serialable接口。
HashMap属性
//实现了序列化，有自己对应的serialVersionUID
private static final long serialVersionUID = 362498820763181265L;
//默认初始容量16(2^4)——必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子0.75 当HashMap中存储的元素的数量大于(容量*负载因子)也就是默认大于16*0.75=12时，HashMap会进行扩容的操作
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;
//是HashMap底层存储的数据结构，是一个Node数组。Node类为元素维护了一个单向链表。
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
//扩容阈值，用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)
int threshold;
//HashMap的加载因子
final float loadFactor;
这里有个问题，到底什么是加载因子呢？还是先继续往下看源码
Map.Entry
这个类应该都比较熟悉了，在对Map进行遍历的时候都会用到这个，不如去看看Map的源码吧。。。
把Map中的结构抽出来看：
//计算整个map中的数据的长度
int size();
//判断map是否为空
boolean isEmpty();
//判断map中是否含有某个key
boolean containsKey(Object key);
//判断map中是否含有某个值
boolean containsValue(Object value);
//用putAll方法把一个Map放入一个新的map中
void putAll(Map<? extends K, ? extends V> m);
//移除map中的所有元素
void clear();
//Entry接口
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
//返回当前Entry对应的哈希码值
int hashCode();
````
}
Node<K,V>
HashMap中有这样一个静态Node类,实现了Map.Entry这个接口。
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;
}
}
从注释里看的话，Node<K,V>是一个基本结点，用于大多数键值对(entries)。LinkedHashMap的Entry继承于HashMap.Node<K,V>；HashMap中的TreeNode继承于LinkedHashMap.Entry<K,V>。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}
不知道为什么TreeNode要继承于LinkedHashMap.Entry，TreeNode是红黑树中的结点结构，还是先继续往下吧。。。
HashMap的构造函数
//无参构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
//是否大于2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
//负载因子的初始值都为0.75
this.loadFactor = loadFactor;
//扩容阈值 调用tableSizeFor方法
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
tabelSizeFor
在计算threshold出现了一个tableSizeFor方法，这个方法到底是干嘛的呢？点进去一看原来又是高效的位运算。源码中基本上都是位运算，这么做一定有它的原因。我试了一下当cap=15的时候，n的结果还为15，返回16；当cap=20的时候，n的结果为31，返回32。还是不知道为什么要这样做，去查了下资料。
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;
}
作用：
tableSizeFor方法保证函数返回值是大于等于给定参数initialCapacity最小的2的次方幂。
也就对应了之前定义的常量DEFAULT_INITIAL_CAPACITY的值为16，注释中说容量必须是2的次幂。根据它的作用来说如果我输入的值在[33,64]之间，那么最后n的结果都为63，且threshold为64。我去试了下，真的是这样。位运算真的是一个很神奇的东西，如果我想运算的值都可以自己用位运算和逻辑运算写出来的话，在计算方面效率确实是可以提高不少。
为什么cap要保持为2的幂次方？
cap要保持为2的幂次方主要原因是HashMap中数据存储有关。在JDK1.8中，HashMap中key的Hash值由Hash(key)方法计算得来。
HashMap中存储数据table的index是由key的Hash值决定的。在HashMap存储数据的时候，我们希望数据能够均匀分布，以避免哈希冲突，所以一般就会采用取余(%)的操作来实现。
有一个重要的知识：取余操作中如果除数是2的幂次方则等价于和其除数减一的与操作
index = e.hash & (newCap - 1)
等价于：
index = e.hash % newCap
putMapEntries
在将Map作为参数传入HashMap的构造函数中的时候调用了这个方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//Node<K,V>[] table为null
if (table == null) { // pre-size
//计算:传进来的map的容量+1.0f
float ft = ((float)s / loadFactor) + 1.0F;
//和最大容量作比较
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//将当前map的容量和扩容阈值作比较，如果超过了阈值就需要执行扩容方法
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();//计算threshold
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);
}
}
}
resize
resize这个方法重新计算了Node<K,V>[] table的容量和扩容阈值
final Node<K,V>[] resize() {
//oldTab是当前的table数组
Node<K,V>[] oldTab = table;
//得到oldTab的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr是当前数组的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;//初始化新的数组容量和扩容阈值
//旧的数组容量大于0
if (oldCap > 0) {
//考虑容量值不能超过2^30
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//扩容后的新数组的容量为旧数组容量的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 扩容阈值也为之前的两倍
}
//旧数组的容量<=0 & 旧数组的扩容阈值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//新数组容量为旧数组的扩容阈值
else {
//newCap=16,newThr=12
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;
//这里主要就是将旧数组中的结点放到新数组中，这里面需要考虑的问题是因为扩容指针数组的长度变为原来的2倍，结点对应的位置可能会发生改变，也就是我们需要处理可能会发生的哈希冲突的问题。
@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;
//判断出当前节点是TreeNode类型，也就是红黑树类型的结点需要做自己的变化
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;
}
//原索引+oldCap
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;
}
解释一
可以看到在这部分多出来了两个新的链表lo和hi。lo存放那些和之前hash表中位置没有改变的结点，hi就用来存放产生了hash冲突的结点。
主要的判断方法就和下面的公式有关：
- (e.hash & oldCap) == 0
- e.hash & (newCap - 1)
- e.hash & (oldCap - 1)
公式2和3都是求当前节点要在hash表中的位置，前面提到过。公式1的效果就是为了判断扩容后结点存在的位置是否发生了改变，结果为true,就说明没有发生改变。也就是公式2和公式3计算出来的效果是一样的。举个栗子:
旧的数组的容量为16，则新的数组的容量为32。计算值的话就是：
e.hash & 0x0F(0000 1111 为15)——旧
e.hash & 0x1F(0001 1111 为31)——新
e.hash & 0x10(0001 0000)——e.hash & oldCap
新数组和旧数组的长度之间会向高位移一个1,也就是说看结点的hash值在对应的高位是1还是0，是0就插入lo队列是0就插入hi队列。
看到了一篇博客上写的，分析的很清楚，图文并茂。。。感觉自己说的不是很清楚。。。java集合——HashMap
putVal
在putMapEntries方法中扩容完会遍历Map集合，获得key和value后调用putVal方法，将key和value作为参数传入。下面来看看这个方法是干嘛的。
见下面
put函数的实现
平常我们会通过调用map.put方法来向集合中放入一个键值对。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前tab数组为null或者长度为0，就进行初始化，调用resize方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果当前Node对应的位置还没有其它结点插入就创建新的结点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//hash值相同且key是同一个对象就覆盖之前的值
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;
}
//如果key值相同就替换
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;//增加修改次数
//超过了扩容阈值，调用resize方法
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal函数的大致思路为：
- 对key的hashCode()做hash，然后再计算index;
- 如果没有碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(>=TREEIFY_THRESHOLD),就把链表转成红黑树；
- 如果结点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了，就调用resize。
get函数的实现
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
实际调用的是getNode方法，看过putVal方法后看get方法就容易许多了
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//检查tab数组不为空且长度大于0且当前单元中有Node结点
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);
//在当前链表中循环遍历查找要找的结点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
getVal的具体流程如下：
- bucket里的第一个节点，直接命中；
- 若第一个未命中，就去遍历查找。一种是在树的结构中查找，一种就是在单链表中查找。
到这里HashMap中的基本重要方法就分析完了，主要有两个属性需要特别关注:
- threshold 扩容阈值
- loadFactor 负载因子
几个方法：
- tableSizeFor():计算扩容阈值
- resize():扩容Node<K,V> tab数组
- putVal():往map中添加值
- getVal():获取map中的值
- hash():计算hashCode()的hash值
这里再对一些地方进行解释：
在java中，散列表用链表数组实现。每个链表被称为桶(bucket)，要想查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得的结果就是保存这个元素的桶的索引
两个重要参数
容量(Capacity)和负载因子(LoadFactor)。
- Capacity:就是bucket的大小
- LoadFactor:就是bucket填满程度的最大比列
如果对迭代性能要求很高的话，不要把Capacity设置过大，也不要把LoadFactor设置过小。当bucket中的entries的数目大于capacity*loadfactor时就需要调整bucket大小为当前的2倍。
hash函数的实现
HashMap中的hash()
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里对key为null还做了处理，key为null,hash后等于0，说明HashMap是支持key为null的。
可以看到这里是对key的hashCode值的前16位和后16位进行异或运算，有一幅图：
image
这里进行取前16位和后16位分别进行异或是为了减少在数组中插入值时产生频繁的碰撞。可以这样去想如果当前的数组长度比较小，比如说是10，那么在进行(n-1)&hash时，使用的其实只是hashcode()值的后一位，那么这样就会很容易产生碰撞。因此通过高16位和低16位异或的操作，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小时)，引起的碰撞。
如果还是产生了碰撞，HashMap设计者使用了红黑树O(logn)去做。
问题总结
HashMap应该是面试中的高频考点了，这里总结一下应该怎么回答问题。
- 讲一讲HashMap?
HashMap底层的数据结构是用数组+链表+红黑树实现的，当链表中节点的个数大于8的时候链表会进行树化，当节点的个数小于等于6的时候会恢复成链表的结构。HashMap默认初始容量为16，容量的大小一般为2的次方幂，HashMap的大小会根据要存入数据的多少进行扩容，有三个重要的值，Capacity容量就是HashMap当前所能放入的所有键值对，loadFactor扩容因子一般为0.75代表填满当前map容量的最大比例，threshold扩容阈值，它的大小为(容量*扩容因子),当要加入值的个数加上之前加入过的值的总和大于扩容阈值需要对HashMap进行扩容，会调用resize函数，map的容量会变为之前的2倍，扩容阈值也会变为之前的两倍。还有常用的加入元素和取出元素的get和put方法，get方法会先去判断当前key的hashCode的hash值，如果存在且是第一个节点就取出，如果不是就去遍历当前的链表，如果当前要查询的节点是红黑树节点就去在树中寻找，否则就去遍历链表。put方法在放入一个entry的时候会先计算hash值并计算index值，也就是当前要放入的节点的位置，如果当前位置为空就创建结点插入，如果之前有节点放入就去遍历检查有没有重复的节点，有就替换现有的节点，保证key的唯一性。
- 为什么使用HashMap?
HashMap是一个散列桶(数组和链表)，它存储的内容是键值对(key-value)映射
HashMap采用了数组和链表的数据结构，能在查询和修改方面继承了数组的线性查找和链表的易于删除抛弃的节点
HashMap是非synchronize的，所以HashMap很快
HashMap可以接受null键和值，但是HashTable不能。(HashMap在key为null时在hash方法中做了处理)
- HashMap线程安全么？还知道其他Map类的集合么？和HashMap有什么区别？
不是线程安全的，在对HashMap的操作中并没有上锁。在多线程访问使用put方法插入元素，发生哈希碰撞可能会造成数据的丢失。还有resize方法也是不安全的，多线程下都会创建一个新的table数组，但最终只有一个对象替换之前的旧的table数组。
了解到的其他Map类:
HashTable:也是数组+链表的存储方式，内部共享数据的方法添加了synchronized，保证了线程安全。
LinkedHashMap:(HashMap+LinkedList)存入的数据是有序的。实现了Lru缓存。
ConcurrentHashMap:引入了CAS,根据同步级别对map的一部分上锁。引入了分割，不论变的多么大仅仅需要锁定map的某个部分，其他的线程不需要等到迭代完成才能访问map
- HashMap的扩容机制是如何实现的？
HashMap的扩容机制要提到三个变量，threshold扩容阈值、loadFactor扩容因子一般都为0.75、capacity容量，这三个变量之间的关系是扩容阈值=扩容因子*总容量，也就是说在往当前map中添加元素的时候会去检查添加的新值加上之前已经有个元素的个数时候会超过当前map的扩容阈值，如果超过了就需要扩容。如果当前容量非常大甚至超过了最大容量2^30，那么就把当前容量设置为Integer.MAX_VALUE,否则就将当前的map容量和扩容阈值都设置为之前的2倍。
- HashMap中的hash方法是怎么实现的？
hash方法其实是根据key的hashCode值，取这个值的前16位和后16位进行异或操作，在通过(n-1)&hash得到当前节点所要放入的数组的下标。
