HashMap是Java程序猿平时用的较多的一种数据结构，也经常会在各种面试中被问起。喜欢看JDK源码的同学肯定会发现随着JDK版本的更新迭代，HashMap的底层实现也在不断地优化,那么本文我们就来聊聊HashMap的实现结构和原理吧
概述
java.util.Map接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap，和TreeMap，类继承关系如下图所示：
1.HashMap：它根据键的hashCode值存储数据，HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，如果需要线程安全，可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
2.Hashtable：Hashtable继承自Dictionary类，线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap使用分段锁。Hashtable不建议使用，需要线程安全的场合可以用ConcurrentHashMap替换。
3.LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，使用Iterator遍历时，先得到的记录肯定是先插入的。
4.TreeMap：TreeMap实现SortedMap接口，保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
存储结构
从JDK1.8之后，HashMap的存储结构使用哈希桶数组+链表/红黑树实现。为了解决哈希冲突，HashMap采用了链地址法，但是这样避免不了链表过长导致HashMap性能严重下降。所以当链表长度超过默认值8的时候，链表就会转为红黑树。红黑树是一棵二叉查找树，但它在二叉查找树的基础上增加了相关特性使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
重要方法
1.tableSizeFor()
源码
/**
* Returns a power of two size for the given target capacity.
*
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;
}
调用的地方
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);
}
HashMap的capacity都是2的幂，这个方法是用于找到大于或者等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数，这就是为什么第一步需要int n = cap -1的原因。
下面看看这几个无符号右移操作：
第一次右移
n |= n >>> 1;
由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1，假设n为01xxxxxxx。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如011xxxxxxxx。
第二次右移
n |= n >>> 2;
此时n为011xxxxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如01111xxxxxx。
第三次右移
n |= n >>> 4;
这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如011111111xxxxxx 。
。。。
以此类推,容量最大也就是32bit的正数，因此最后n |= n >>> 16 ，最多也就32个1，但是这时已经大于了MAXIMUM_CAPACITY ，所以取值到MAXIMUM_CAPACITY,不大于MAXIMUM_CAPACITY的时候则n+1,这样就华丽丽的取到了大于或等于n的那个最大2次幂值，作为HashMap的容量。还是蛮巧妙的一个算法哈~
2.hash()
1.8版本
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.7版本
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这段代码其实叫扰动函数，为啥要这样搞呢，不能取到key的hashCode的时候直接用下面的方法去求模找对应哈希桶数组的下标位置吗？
static int indexFor(int h, int length) {
//jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1);
}
顺带说一下，这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个"低位掩码"。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是<b>00000000 00000000 00001111</b>。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
10100101 11000100 00100101
00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部归零，只保留末四位
但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就无比蛋疼。
这时候“<b>扰动函数</b>”的价值就体现出来了，说到这里大家应该猜出来了。看下面这个图:
向位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
但明显Java 8觉得扰动做一次就够了，像1.7做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。
网友评论