在日常开发工作中，HashMap是使用频率相当高的一个工具，同时「HashMap」的底层实现和原理，也成了面试题中的常客。最近又翻看了一下源码，做个记录。(本文都是基于jdk1.8的源码)
1. 谈一下HashMap的特性。
-
HashMap的实现框架是「数组 + 链表」的组合方式。 -
HashMap存储键值对实现快速存取. -
HashMap的value可为null. -
数组中的index 是根据hashcode算出来的，所以是无序的。 -
非同步，线程不安全。 -
key值不可重复， put()方法，如果key值重复则覆盖。putIfAbsent()方法，如果key重复且value == null才会覆盖。
2.HashMap的底层原理是什么？
「HashMap」底层的数据结构是「Hash表」 即 「数组+链表/红黑树」 的组合方式。
基于数组+链表的结构，我们可以思考一下两个问题
「1.」 如果每个(k,v) 都在 某个index 下的链表里面，其他index 没有值会浪费数组其他位置的空间。
「2.」 如果数据均匀分配情况下链表变长了，查询依然可能存在问题。(链表达到一定长度会转变成红黑树)。
所以HashMap 需要解决，
1). 数据均匀分配的问题。
2). 链表红黑树相互转化。
3. HashMap put get 是如何实现的？
1. 我们来看一下「具体put方法是怎么实现的」
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 这里取key的哈希值与高16位做异或运算得出的值作为 运算数组index的一个值.
* 为啥不直接用hashCode , 如果直接用hashCode 的话，数据就不随机了，容易分布不均匀。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* put方法的核心逻辑
* @param hash 取Key的对象的hashCode
* @param onlyIfAbsent
false: key值重复则覆盖。
ture: key重复且`value == null` 才会覆盖。
* @param evict 这里是false
false: 表示在初始化HashMap
true: 表示不再初始化的状态，通过方法afterNodeInsertion(boolean evict) 回调HashMap的状态。
* @return 如果是新加入的value 返回为null, 如果key重复返回旧的 value
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 1. 第一次添加value 需要初始化数组的长度。
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 2. 如果hashMap没有这个key , 用 数组长度n减去1 和 hash 做与运算得出index, 并把(k,v)存入。
tab[i] = newNode(hash, key, value, null);
else {
// 否则hashMap有这个key
HashMap.Node<K,V> e; K k;
// p 表示这个index 下对应的链表/红黑树的第一个结点(不一定是当前put的(k,v) )
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 3. 如果 hash 一致并且 两个key相等才认为是同一个对象
// 然后把这个值赋给 e, e 的值是否覆盖取决于 onlyIfAbsent
e = p;
else if (p instanceof HashMap.TreeNode)
// 4. 如果为树，同样 如有一样的值返回对应的引用，没有添加到树中再返回对应引用。
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 5. 遍历链表如果找到这个值 把值赋给e, e 的值是否覆盖取决于 onlyIfAbsent
// 如果没找到，创建(k,v)的Node，插入到链表的尾部
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
// TREEIFY_THRESHOLD = 8 如果链表长度超过阈值，则 链表->红黑树
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)
//onlyIfAbsent false 覆盖
//true 并且旧值为null 覆盖
e.value = value;
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 记录HashMap操作次数，用来在并发操作的时候判断是否要快速失败(fail-fast) 并抛出异常ConcurrentModificationException
++modCount;
// threshold 阈值 当HashMap中的(k,v)数量 > threshold 会扩容
if (++size > threshold)
resize();
// 回调HashMap的状态
afterNodeInsertion(evict);
// 新put的返回null
return null;
}
「步骤1」：若哈希table为null，或长度为0，则初始化数组的长度；
「步骤2」：根据index找到目标数组后，若当前数组上没有结点，那么直接新增一个结点，值赋在当前index；
「步骤3」：若当前数组对应index上有链表，且头结点就匹配，那么直接做替换即可；
「步骤4」：若当前数组对应index上是树结构，则转为红黑树的插入操作；
「步骤5」：若步骤1、2、3、4都不成立，则对链表做遍历操作。
-
若链表中有结点匹配，则做value替换； -
若没有结点匹配，则在链表末尾追加。同时，执行以下操作：
i) 若链表长度大于TREEIFY_THRESHOLD，则执行红黑树转换操作；
ii) 若「条件i)」 不成立，则执行扩容resize()操作。
以上5步都执行完后，再看当前Map中存储的k-v对的数量是否超出了threshold，若超出，还需再次扩容。
2. get 方法的实现
了解了上面的put()操作，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 && // 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;
}
先根据key计算hash值，进一步计算得到哈希table的目标index，若此位置上为红黑树，则再红黑树上查找，若不是红黑树，遍历链表。
4. HashMap里面的key为什么重写equals，hashcode？
看完put的流程, 再思考一下这个问题，为什么重写equals，hashcode？
「换个问题其实就是：作为HashMap的Key需要满足什么样的条件。」
-
「相等（相同）的对象必须具有相等的哈希码（或者散列码）」 -
「如果两个对象的hashCode相同，它们的值不一定相等(相同)」
但是Java对象的eqauls方法和hashCode方法是这样规定的：
「1、对于两个对象来说，如果使用equals方法比较返回true，那么这两个对象的hashCode值一定是相同的；。」
「2、对于两个对象来说，如果使用equals方法返回false，那么这两个对象的hashCode值不要求一定不同（可以相同，可以不同），但是如果不同则可以提高应用的性能。」「3、对于Object类来说，不同Object对象的hashCode值是不同的（Object类的hashcode值表示的是对象的地址）」
根据第二个规定，同一个hashCode对应不同的对象，在put的时候，HashMap会认为这是一个Key,但根据java的规定，这是两个对象。
❝
在object类中，hashcode()方法是本地方法，返回的是对象的地址值，而object类中的equals()方法比较的也是两个对象的地址值，如果equals()相等，说明两个对象地址值也相等，当然hashcode()也就相等了；在String类中，equals()返回的是两个对象内容的比较，当两个对象内容相等时，Hashcode()方法根据String类的重写代码的分析，也可知道hashcode()返回结果也会相等。以此类推，可以知道Integer、Double等封装类中经过重写的equals()和hashcode()方法也同样适合于这个原则。当然没有经过重写的类，在继承了object类的equals()和hashcode()方法后，也会遵守这个原则。「所以我们一般用这些不可变的对象作为HashMap的Key，这样就不会造成两个不同对象的hashCode一样的时候，相互覆盖的问题了。」
❞
public boolean equals(Object obj) {
return (this == obj);
}
public native int hashCode();
如果都不重写: hashMap put值的时候，这个key的值一样，但是地址不一样，这样HashCode会认为是两个key 如果只重写equals: put的时候，同上 如果只重写hashCode: hashCode一样，则equals也一样，但是值不一定一样，因为equals对比的是地址。
-
Hash的主要原理就是把大范围映射到小范围；所以，你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。 -
由于Hash逼近单向函数；所以，你可以用它来对数据进行加密。 -
不同的应用对Hash函数有着不同的要求；比如，用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
１、「加法Hash」所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下：
static int additiveHash(String key, int prime){
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}
这里的prime是任意的质数，看得出，结果的值域为[0,prime-1]。
２、「位运算Hash」这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。比如，标准的旋转Hash的构造如下：
static int rotatingHash(String key, int prime){
int hash, i;
for (hash=key.length(), i=0; i<key.length(); ++i)
hash = (hash<<4)^(hash>>28)^key.charAt(i);
return (hash % prime);
}
３、「乘法Hash」 这种类型的Hash函数利用了乘法的不相关性（乘法的这种性质，最有名的莫过于平方取头尾的随机数生成算法，虽然这种算法效果并不好）。比如，
static int bernstein(String key){
int hash = 0;
int i;
for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
return hash;
}
jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过，它使用的乘数是31。推荐的乘数还有：131, 1313, 13131, 131313等等。
5.平时在使用HashMap时一般使用什么类型的元素作为Key？
看过第4个问题，这个就显而易见了
一般选择Integer，String这种不可变的类型，像对String的一切操作都是新建一个String对象，对新的对象进行拼接分割等，这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的。
6. HashMap中hash函数是怎么实现的？为什么不直接将key作为哈希值而是与高16位做异或运算？还有哪些hash函数的实现方式？
可以结合put的过程理解一下
/**
* 这里取key的哈希值与高16位做异或运算得出的值作为 运算数组index的一个值.
* 为啥不直接用hashCode , 如果直接用hashCode 的话，数据就不随机了，容易分布不均匀。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-
「对key的hashCode做hash操作，与高16位做异或运算」
-
「因为数组位置的确定用的是与运算，仅仅最后四位有效，设计者将key的哈希值与高16为做异或运算使得在做&运算确定数组的插入位置时，此时的低位实际是高位与低位的结合，增加了随机性，减少了哈希碰撞的次数。」
7. hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？
「调用场景：」
1.初始化数组table 时
2.当数组table的size达到阙值时即++size > load factor * capacity 时，也是在putVal函数中
「扩容逻辑代码如下」
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)
// 阈值和数组容量都扩大二倍。
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//第一次put时用的数组容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 默认的数组大小和阈值
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) {
//1. 遍历数组
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//拿到链表或者红黑树
oldTab[j] = null;
if (e.next == null)
// 若只有一个结点，则直接运算新的index存储。
// 这里的结果和下面的算法一样,两种情况
// 如果(e.hash & oldCap) == 0，那么e.hash & (newCap - 1)的结果其实和原来的一样 = j
// 如果(e.hash & oldCap) == 0，那么e.hash & (newCap - 1)的结果大于e.hash&(oldCap-1)
// 并且不会和其他的冲突(为什么不冲突下面有说明)，所以直接赋值了。
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// "lo"前缀的代表要在原bucket上存储，"hi"前缀的代表要在新的bucket上存储
// loHead代表是链表的头结点，loTail代表链表的尾结点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 这里以oldCap=8为例 ，‘*’ 表示可能为0或1
// 0001 1000 e.hash=24
// 0000 1000 oldCap = 8
// 0001 0000 newCap = 16
/* 如果e.hash & oldCap == 0 说明 e.hash = **** 0***
那么 e.hash & (newCap-1) 如下
**** 0*** e.hash
& 0000 1111 newCap-1
= 0000 0*** 这个值和e.hash&(oldCap-1) 是一样的，所以不用换位置
*/
/*
如果e.hash & oldCap != 0 说明 e.hash = **** 1***
那么 e.hash & (newCap-1) 如下
**** 1*** e.hash
& 0000 1111 newCap-1
= 0000 1*** 这个值大于e.hash&(oldCap-1) ,所以需要换位置
基于这个结果，也可以得出，如果e.hash不一样，e.hash & (newCap - 1)的结果一定不一样，这里也解释了上面直接赋值的问题。
*/
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;
//这里的 j + oldCap 其实是和 e.hash&(newCap - 1) 是一个值
//原因可以参照上面的演算
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
8. HashMap容量为2次幂的原因？
了解了前几个问题这个就很容易回答了。
HashMap是hash表（数组+链表）的结构，需要每个值尽可能的均匀分配到数组上，又因为在put的时候是通过 hash和(数组长度-1)取与(&)的运算方式，所以(数组-1)=11111 才能做到均匀的取到每个值。「这个也是为啥每次扩容都乘以2的原因」。
9. 「传统hashMap的缺点(为什么引入红黑树？)：」
JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。
10. 谈谈1.7 扩容时导致死循环的问题。
先看下JDK7中的扩容代码片段：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//这里会新建一个更大的数组，并通过transfer方法，移动元素。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
其实就是简单的链表反转，再进一步简化的话，分为当前结点e，以及下一个结点e.next。我们以链表a->b->c->null为例，两个线程A和B，分别做扩容操作。
-
「线程A和B」各自新增了一个新的哈希table，「线程B」刚执行完 Entry < K,V > next = e.next，此时「线程B」中，e.next=b -
这时cpu切换到「线程A」并做完扩容操作后 -
「线程B」才继续开始扩容。此时对于「线程B」来说，当前结点 e指向a结点，下一个结点e.next仍然指向b结点（此时在「线程A」的链表中，已经是c->b->a的顺序）。然后继续移动，e=e.next即e=b,此时b已经指向a了，然后继续执行，找到b.next ，此时a.next = null , 头插法然后把a 指向b, 结束 ，这样a和b就相互引用了，形成了一个环；
11. 多线程环境下使用HashMap，会引起各类线程不安全的问题。
-
死循环 (1.8已经解决) -
数据重复 -
数据丢失（覆盖）
12. 怎么解决线程安全问题。
-
可以用ConcurrentHashMap代替。 -
Collections.SynchronizedMap()用这个方法给map的操作方法加上锁synchronized
原文始发于微信公众号（TodoCoder）：HashMap你了解多少
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/169096.html
