HashMap 是作为最常用的集合类之一，是面试中的高频问题。一些简单套路例如增删改查时间复杂度，都已经被玩坏了。这篇文章介绍一个一些HashMap中不被人注意的小细节
HashMap概况
HashMap的存储结构
- hashMap实际保存是在一个 Node数组里面，这个Node其实就是Key--> value存储结构的部分。Node这个类含有三个属性，key，value，和hash值
- 整体是以单链表的形式链接起来的
- Key是以数组的形式存储。
- Value 是以单链表的形式存储
这样的存储结构结构保证了增删改查时间复杂度的都可以是O（1）常数级别。
关于HashMap的一些小细节
- 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
- 通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
- 如果两个Key的hash发生碰撞，但是equals方法没有相等，会发生什么？
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;
//通过hash计算出来的下标没有node的话，那么就把这个node填充
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果hash和equals计算均相等。会提换原来的元素
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) {
//如果hash值计算的相同，但是equals计算的不同，则会放到链表的最后
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方法的具体实现，也可以看出，为什么HashMap的Key为什么要同时重写hashCode和equlas方法。同样的，你可以查看get方法的具体实现。其实这样是一个对Hash冲突的解决办法。
HashMap中对Key的 HashCode的处理？
首先看一段代码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这段代码的意思是，高位和低位进行扰动计算。
-
为什么进行扰动计算？ 首先，扰动计算后的代码HashMap是一个Hash桶加上链表。在用过key计算出的Hash值，我们知道是一个 32位的值。但是我们需要的hash值有效长度没有那么多。可能只有hashMap。key数组那么长的长度即可。但是带来的问题是，我们key的hash值在length的范围内很有可能不是 均匀分布的。很有可能带来hash冲突。
查看知乎上的回答 -
HashTable 的Key为什么不能为null
- 看HashTable源代码的put方法实现。可以看key的hash计算方法。当然会出现空指针错误了
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
