JavaHashMap原理解析

本文分析HashMap的实现原理。

数据结构&＃xff08;散列表&＃xff09;

HashMap是一个散列表&＃xff08;也叫哈希表&＃xff09;&＃xff0c;用来存储键值对(key-value)映射。散列表是一种数组和链表的结合体&＃xff0c;结构图如下&＃xff1a;

简单来说散列表就是一个数组&＃xff08;上图纵向&＃xff09;&＃xff0c;数组的每个元素是一个链表&＃xff08;上图横向&＃xff09;&＃xff0c;类似二维数组。链表的每个节点就是我们存储的key-value数据&＃xff08;源码中将key和value封装成Entry对象作为链表的节点&＃xff09;。

哈希算法

对于散列表&＃xff0c;不管是存值还是取值&＃xff0c;都需要通过Key来定位散列表中的一个具体的位置&＃xff08;即某个链表的某个节点&＃xff09;&＃xff0c;计算这个位置的方法就是哈希算法。

大概过程是这样的&＃xff1a;

1. 用Key的hash值对数组长度做取余操作得到一个整数&＃xff0c;这个整数作为数组中的索引得到这个索引位置的链表。
2. 得到链表之后&＃xff0c;就可以存值和取值了。
   如果是存值&＃xff0c;直接把数据插入到链表的头部或者尾部即可&＃xff08;或者已存在就替换&＃xff09;&＃xff1b;
   如果是取值&＃xff0c;就遍历链表&＃xff0c;通过key的equals方法找到具体的节点。

例如一个key-value对要存到上图的散列表里&＃xff0c;假设key的哈希值是17&＃xff0c;由图可知&＃xff08;纵向&＃xff09;数组长度是16&＃xff0c;那么17对16取余结果是1&＃xff0c;数组中索引1位置的链表是 1->337->353 &＃xff0c;所以这个key-value对存储到这个链表里面&＃xff08;插到头还是尾可能不同Java版本不一样&＃xff09;。如果是取值&＃xff0c;就遍历这个链表&＃xff0c;由于这个链表每个节点的key的哈希值都一样&＃xff0c;所以根据equals方法来确定具体是哪个节点。

通过上面的哈希算法&＃xff0c;可以有如下结论&＃xff1a;

• 不同的key具体相同的哈希值叫做哈希冲突&＃xff0c;HashMap解决哈希冲突的方法是链表法&＃xff0c;将具有相同哈希值的key放在同一个链表中&＃xff0c;然后利用key类的equals方法来确定具体是哪个节点。
• Key的唯一性是通过哈希值和equals方法共同决定的&＃xff0c;所以想要用一个类作为HashMap的键&＃xff0c;必须重写这个类的hashCode和equals方法。同理&＃xff0c;HashSet是基于HashMap实现的&＃xff0c;它没有重复元素的特点是利用HashMap没有重复键实现的。所以&＃xff0c;Set集合里面的元素类&＃xff0c;也必须同时实现hashCode方法和equals方法。
• HashMap存储的数据是无序的。

为什么HashMap大小是2的整数次幂的时候效率最高

哈希算法主要分两步操作&＃xff1a;1.通过哈希值定位一个链表&＃xff1b; 2.遍历链表&＃xff0c;通过equals方法找到具体节点。为了使哈希算法效率最高&＃xff0c;应该尽量让数据在哈希表中均匀分布&＃xff0c;因为那样可以避免出现过长的链表&＃xff0c;也就降低了遍历链表的代价。
如何保证均匀分布&＃xff1f;前面的哈希算法说到&＃xff0c;通过取余操作将Key的哈希值转换成数组下标&＃xff0c;这样可以认为是均匀的。但是&＃xff0c;源码中并没有直接用%操作符取余&＃xff0c;而是使用了更高效的与运算&＃xff0c;源码如下&＃xff1a;

/*** Returns index for hash code h.*/
static int indexFor(int h, int length) {// assert Integer.bitCount(length) &＃61;&＃61; 1 : "length must be a non-zero power of 2";return h & (length-1);
}

这样就多了一些限制&＃xff0c;因为只有当length是2的整数次幂的时候&＃xff0c;h & (length-1) &＃61; h % length才成立。当然&＃xff0c;如果length不是2的整数次幂&＃xff0c;h & (length-1)的结果也一定比length小&＃xff0c;将Key转换成数组下标也没什么问题&＃xff0c;但是&＃xff0c;这样会导致元素分布不均匀严重影响散列表的访问效率。看下面的一个示例代码&＃xff1a;

解释一下图中的代码&＃xff0c;随机生成一组Key&＃xff0c;然后利用与运算&＃xff0c;把key全部转换成一个数组容量的索引&＃xff0c;这样就得到一组索引值&＃xff0c;这组索引中不相同的值越多&＃xff0c;说明分布越均匀&＃xff0c;输出结果的result就是 “这组索引中不相同的值的数量”。
从运行结果来看&＃xff0c;容量是64的时候相比于其他几个容量大小&＃xff0c;分布是最均匀的。容量是65的时候&＃xff0c;每次结果都是2&＃xff0c;原因很简单&＃xff0c;当容量是65的时候&＃xff0c;下标&＃61;h&64&＃xff0c;64的二进制是1000000&＃xff0c;很明显&＃xff0c;与它进行与运算的结果只有两种情况&＃xff0c;0和64&＃xff0c;也就是说&＃xff0c;如果HashMap大小被指定成65&＃xff0c;对于任意Key&＃xff0c;只会存储到散列表数组的第0个或第64个链表中&＃xff0c;浪费了63个空间&＃xff0c;同时也导致0和64两个链表过长&＃xff0c;取值的时候遍历链表的代价很高。容量66和67的结果是4同理。如果容量是64&＃xff0c;那么下标&＃61;h&63&＃xff0c;63的二进制是111111&＃xff0c;每一位都是1&＃xff0c;好处就是对于任意Key&＃xff0c;与63做与运算的结果可能是1-63的任意数&＃xff0c;很多Key的话自然就能分布均匀。
通过这个示例代码的分析就可以找到一个规律了&＃xff0c;容量length&＃61;2^n 是分布最均匀&＃xff0c;因为length-1的二进制每一位都是1&＃xff1b;相反的length&＃61;2^n&＃43;1是分布最不均匀的&＃xff0c;因为length-1的二进制中的1数量最少。

结论&＃xff1a;HashMap大小是2的整数次幂的时候效率最高&＃xff0c;因为这个时候元素在散列表中的分布最均匀。

从上面的分析来看&＃xff0c;使用与运算虽然效率高了&＃xff0c;但是增加了使用限制&＃xff0c;如果用%取余的做法&＃xff0c;那么对于任何大小的容量都能做到均匀分布&＃xff0c;可以把图中代码int a &＃61; keySet[j] & (c - 1); 改成 int a &＃61; keySet[j] % c;试一下。

HashMap的容量

通过上面的分析&＃xff0c;容量是2的整数次幂的时候效率最高&＃xff0c;那么很容易想到&＃xff0c;如果随着数据量的增长&＃xff0c;HashMap需要扩容的时候是2倍扩容&＃xff0c;区别于ArrayList的1.5倍扩容。
那么什么时候扩容呢&＃xff1f;首先说明一下&＃xff0c;我们所说的HashMap的容量是指散列表中数组的大小&＃xff0c;这个大小不能决定HashMap能存多少数据&＃xff0c;因为只要链表足够长&＃xff0c;存多少数据都没问题。但是&＃xff0c;数据量很大的时候&＃xff0c;如果数组太小&＃xff0c;就会导致链表很长&＃xff0c;get元素的效率就会降低&＃xff0c;所以我们应该在适当的时候扩容。源码默认的做法是&＃xff0c;当数据量达到容量的75%的时候扩容&＃xff0c;这个值称为负载因子&＃xff0c;75%应该是大量实验后统计得到的最优值&＃xff0c;没有特殊情况不要通过构造方法指定为其他值。
扩容是有代价了&＃xff0c;会导致所有已存的数据重新计算位置&＃xff0c;所以&＃xff0c;和ArrayList一样&＃xff0c;当知道大概的数据量的时候&＃xff0c;可以指定HashMap的大小尽量避免扩容&＃xff0c;指定大小要注意75%这个负载因子&＃xff0c;比如数据量是63个的话&＃xff0c;HashMap的大小应该是128而不是64。

对于容量的计算&＃xff0c;源码已经封装好了一个方法

/*** Returns a power of two size for the given target capacity.*/
static final int tableSizeFor(int cap) {int n &＃61; cap - 1;n |&＃61; n >>> 1;n |&＃61; n >>> 2;n |&＃61; n >>> 4;n |&＃61; n >>> 8;n |&＃61; n >>> 16;return (n <0) ? 1 : (n >&＃61; MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n &＃43; 1;
}

此方法在HashMap的构造方法中被调用&＃xff0c;所以指定容量的时候无需自己计算&＃xff0c;比如数据量是63&＃xff0c;直接new HashMap<>(63)即可。

HashMap的遍历

前面提到一点&＃xff0c;散列表中的链表的节点是Entry对象&＃xff0c;通过Entry对象可以得到Key和Value。HashMap的遍历方法有很多&＃xff0c;大概可以分为3种&＃xff0c;分别是通过map.entrySet()、map.keySet()、map.values()三种方式遍历。比较效率的话&＃xff0c;map.values()方式无法得到key&＃xff0c;这里不考虑。比较map.entrySet()和map.keySet()的话&＃xff0c;结合散列表的结构特点&＃xff0c;很明显map.entrySet()直接遍历Entry集合&＃xff08;所有链表节点&＃xff09;取出Key和Value即可&＃xff08;一次循环&＃xff09;&＃xff0c;map.keySet()遍历的是Key&＃xff0c;得到Key之后在通过Key去遍历相应的链表找到具体的节点&＃xff08;多个循环&＃xff09;&＃xff0c;所以前者效率高。

扩展&＃xff1a;LinkedHashMap和LruCatch

对于LinkedHashMap的理解&＃xff0c;我觉得一张图就够了&＃xff1a;

在散列表的基础上加上了双向循环链表&＃xff08;图中黄色箭头和绿色箭头&＃xff09;&＃xff0c;所以可以拆分成一个散列表和一个双向链表&＃xff0c;双向链表如下&＃xff1a;

上面两张图片来自&＃xff1a;https://www.cnblogs.com/xiaoxi/p/6170590.html

然后使用散列表操作数据&＃xff0c;使用双向循环链表维护顺序&＃xff0c;就实现了LinkedHashMap。

LinkedHashMap有一个属性可以设置两种排序方式&＃xff1a;

private final boolean accessOrder;

false表示插入顺序&＃xff0c;true表示最近最少使用次序&＃xff0c;后者就是LruCatch的实现原理。

LinkedHashMap和LruCatch的具体实现细节这里就不分析了。