HashMap解析
注：本文是以Android中的HashMap进行讲解
问题：
1、HashMap采用的是什么数据结构？
2、HashMap默认容量多少？
3、HashMap最大容量多大？
4、HashMap每次扩容多大？
5、HashMap扩容的阈值是多少？默认阈值加载因子是多少？
6、HashMap的hash函数是怎么实现的？还有哪些实现方式？
7、HashMap get的工作原理是什么？
8、HashMap put的工作原理是什么？
9、HashMap如果解决冲突的？
10、HashMap是否是线程安全？如果不是该如何实现线程安全？
11、HashMap使用怎么类型作为key更优？
下面我们带着这些问题，借助源码一一解析HashMap。
问题1：HashMap采用的是什么数据结构？
HashMap基于哈希表的原理，采用数组+链表的数据结构实现的。
哈希表：hashtable，也叫散列表，是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中的一个位置来访问记录。这个映射行数叫散列函数，存放记录的数组叫散列表。
简单的理解哈希表就是一种存储键-值对的数据结构，根据键可以快速访问到对应的值。
我们看下HashMap中关于数据结构的代码：
// Node数组表示哈希表
transient Node<K,V>[] table;
// Node类数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//...省略
}
通过上面的代码验证了HashMap采用的是数组+链表的数据结构，其中数组时Node数组，而Node采用的单向链表结构。
可以想一想为什么采用数组+链表的数据结构？后面我们会解答此问题。
问题2：HashMap默认容量多少？
HashMap默认容量是16，我们直接看代码：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
定义了默认的容量为16，且其注释中还明确了必须是2的多次方。
问题3：HashMap最大容量多大？
HashMap实际最大容量是Integer.MAX_VALUE，我们看下其源码的对最大容量的定义：
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
明明人家定义最大值是2^30，为什么你说是Integer.MAX_VALUE？我们来看下当HashMap扩容时的一段代码：
final Node<K,V>[] resize() {
//...省略
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//...省略
}
上述代码已经很明确了，如果容量大于MAXIMUM_CAPACITY，那么是允许扩容到Integer.MAX_VALUE的。
问题4：HashMap每次扩容多大？
我们先看下HashMap中每次扩容的实现部分的代码：
//HashMap扩容实现方法
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) {
//如果当前容量大于0
if (oldCap >= MAXIMUM_CAPACITY) {
//如果当前容量大于MAXIMUM_CAPACITY值直接扩容到 Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//正常情况下，扩容到原来的1倍；阈值也增加到原来的1倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果当前容量为0，则容量=阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/** 如果容量为0，并且阈值为0，则设置容量为默认容量16，阈值=默认容量*默认加载因子=0.75*16
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
/**
如果新的阈值为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;
//...省略
}
通过上面的代码可以知道，HashMap每次扩容可能是不一样的，总结为：
- 如果当前容量的大于预设最大值MAXIMUM_CAPACITY ，则取值为Integer.MAX_VALUE
- 如果DEFAULT_INITIAL_CAPACITY<当前容量2 <MAXIMUM_CAPACITY,则新的容量和新的阈值设置为当前容量2
- 如果当前容量为0并且当前阈值大于0，则新的容量=当前阈值
- 如果当前容量为0并且当前阈值也未0，则新的容量=默认容量的值=16
同时，通过上面的代码可以知道每次扩容，阈值的值均为重新设置为新容量加载因子，默认情况下即新容量0.75
问题5：HashMap扩容的阈值是多少？默认阈值加载因子是多少？
通过问题4中列出的源码知道，扩容的阈值=新容量加载因子，默认情况下即新容量0.75。阈值用于判断是否进行扩容，当散列表的容量大于阈值或者容量为0时就进行扩容操作。默认的阈值加载因子=0.75，我来看默认加载因子的代码定义：
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
问题6：HashMap的hash函数是怎么实现的？还有哪些实现方式？
hash函数就是散列函数，用于计算键相关的函数，可以理解计算为记录的映射地址。看源码实现：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果key为空，则hash的值为0；如果不为0则值为key的hashCode值亦或上key的hashCode右移16位之后的值。
HashMap 散列函数属于直接定址法，散列函数的实现方式还有：数字分析法、折叠法、随机数法、除留余数法。下面对这几中方式做个简单的说明：
- 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
- 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
- 随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
- 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
问题7：HashMap get的工作原理是什么？
首先我们先看下HashMap中get的实现代码：
public V get(Object key) {
Node<K,V> e;
//通过getNode的方式实现取值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
hash: 经过散列函数计算key得到值
key: 键值
*/
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) {
// tab即散列表，通过(n - 1) & hash计算出映射的地址，即下标
//
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 如果查出的第一个记录hash值相等并且key地址相等或者值相等，则直接放回记录中的值
return first;
// 遍历链表，知道找到匹配的hash或者key
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);
}
}
// 如果散列表为空或者根据hash查找到的记录为空，则返回空
return null;
}
通过上述源码，get的实现是：
1、通过hash函数算出键的hash值
2、接着对hash进行(n - 1) & hash位运算，得出散列表的下标
3、通过散列表的下标得到链表表头
4、在链表中遍历查找，直到找到匹配的记录，最后返回找到的记录的值。匹配查找的条件是：hash值相等并且key地址相等或者值相等
问题8：HashMap put的工作原理是什么？
我们也是先看put的源码，借助源码来了解其实现原理：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
hash: 对键进行hash()操作之后的值
key：键
value: 键对应的值
onlyIfAbsent：true: 原来的值不为空时，则不改变值
evict：false: 散列表处于创建模式，HashMap用不到，LinkedHashMap才有用到，此处不做说明
*/
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;
// 通过（n - 1）& hash取得链表所在散列表的下标
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果匹配的链表为空，则创建链表
tab[i] = newNode(hash, key, value, null);
else {
// 如果匹配的链表不为空，则遍历链表，找到链表中匹配的节点，然后替换其中的值
// e：链表中的节点；k： 节点的键
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)
// 如果链表是树形结构，则使用树形结构的方式实现put,此处不做这块的说明
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;
}
}
// HashMap修改次数加1
++modCount;
// HashMap大小加1，如果HashMap的大小大于阈值则进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
根据put源码，我们可以总结HashMap的put操作的原理为：
1、如果散列表为空，则先创建默认容量的散列表
2、通过(n - 1) & hash 计算的散列表的下标，根据下标获取散列表中的链表
3、如果链表为空，代表插入新的节点，则创建新的链表（节点）插入散列表中
4、如果链表不为空，则遍历链表，判断是否已经存在节点：如果链表中不存在节点，则创建新节点插入链表的表尾；如果链表中已经存在节点则更改原来节点的值
5、如果是插入节点操作，HashMap的大小进行加1处理；如果是更新节点值操作，则不加1处理，并返回旧值
6、如果HashMap的大小加1了，判断HashMap的大小是否大于阈值，如果大于，则进行扩容处理
问题9：HashMap如果解决哈希表冲突的？
首先我们先看下哈希表冲突是什么鬼：对于不同的key经过散列函数计算之后，得到同一散列地址，这种现象称为冲突。试想一些如果哈希表采用的是一维数组，key经过hash()操作之后的值作为下标，value作为数组的值，那么就会出现key不同而下标相同，就会导致前面添加的键值对被后面添加的键值对覆盖的现象。
搞懂了什么是哈希表冲突，那么HashMap是怎么解决这个问题的呢？认真阅读的你，会在前面的问题中找到答案。
没错，通过问题8中put操作的源码，知道当key经过hash()操作，再经过(n -1） & hash得到散列表的下标，即便key计算得到的下标下同，是可以通过链表得到解决的。
总结来说HashMap解决哈希表冲突的方案是链址法，即使用一维数组作为散列表，单链表作为数组的值，当出现冲突时，将值插入链表中即可。
问题10：HashMap是否是线程安全？如果不是该如何实现线程安全？
答案可定不是线程安全的，明显通过上述get和put的源码可以看到，读写操作没有任务的同步、加锁操作，所以HashMap并非线程安全。
那么怎么实现线程安全呢？
1、使用HashTable
2、使用Collections.synchronizeMap处理Hashmap:
Map m = Collections.synchronizeMap(hashMap);
3、使用ConcurrentHashMap
1和2性能较差，推荐使用第三种，ConcurrentHashMap使用的是CAS轻量级锁，性能更好。至于为什么后面为用专门的章节来讲解。
问题10：HashMap使用怎么数据类型作为key更优？
这个是涉及HashMap优化处理的部分，没有做过这方面优化的同学估计一脸懵逼，还有这讲究？
首先我们知道哈希表存在冲突的情况，较少冲突碰撞的概率，提高查找效率；再者get和put的操作会出现频繁的调用key的hashcode()、equal。所以对key进行优化就变得更会重要，首先要解决的较少冲突、接着提高hashcode()和equal的操作。哪些数据类型先天有这方面的优势呢？答案是String和基本数据的wrapper对象（比如Integer、Short、Long等）。为什么呢，看过源码的同学应该能很快知道答案，原因是：
1、这些类是不可变的，都是final，不可继承，没有子类可以改变其实现，而且这些类的值都是不可变的，都有final类型修饰。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象
3、这些类都重写了hashcode()和equal方法，可以确保不同对象返回的hashcode值不一样，减低冲突概率；其中String还对hash进行的缓存处理，提高hashCode的效率。重写equal方法能区别键值的正确性。
