分析HashMap的散列表设计

2018-06-04  本文已影响0人  刘惜有

HashMap是Map接口的一个实现。Map的实现都是一个容器，用于存储键值对。

Map并不一定要通过散列表实现，事实上Map结构符合索引的思想，树、散列表、线性表都可以实现Map

HashMap使用散列表这种数据结构来对映射进行管理。散列的查找算法分为两步。第一步是用散列函数将被查找的键转换为数组的一个索引；第二步是处理碰撞冲突的过程，如拉链法和线性探测法。散列表将key通过一个散列函数映射到对应的value，理论上查找和插入的速度都可以达到O(1)。

散列表是算法在时间和空间上作出权衡的典型例子。如果没有内存限制，可以直接将键作为数组的索引，那么所有的查找操作只需要访问内存一次即可完成。但这种理想情况不会经常出现，因为键很多时需要的内存很大。另一方面，如果没有时间限制，可以使用无序数组并顺序查找，这样就只需要很少的内存。散列表使用了适度的空间和时间并在这两个极端之间找到了平衡。

散列表最大的问题就是冲突，极端冲突情况下，由于散列函数本身的运算，散列表的效率甚至不如遍历，所以要实现基于散列表的结构，最主要的问题就是解决冲突，Hash Map也不例外，解决冲突主要从两个方面下手：

散列函数用于定位元素。数据结构理论中，散列函数一般采用直接定址、除留余数、折叠、数学分析等几种方法。而如果多个元素被定为到同一个位置就需要处理冲突，处理冲突有开放定址、再散列、链地址等多种方法。

散列表的简单实现

在说HashMap的散列表实现之前，我们先来实现一个简单的散列表。

前面提到散列表实现主要就是确定一个散列函数和冲突处理规则。所以实现一个散列表这个问题就变成了如何确定合适的散列函数和冲突处理。

散列函数

首先是散列函数，最简单的散列函数就是直接定址法。所谓直接定值法其实就是将一个一次函数作为散列函数。

hash(k) = ak + b

这种散列函数运算简单且高效，而且冲突率很低，非常适合key范围小的散列表，但是对于key范围特别大的散列表，则需要非常大的散列空间范围。于是就有了接下来的改进方法。

除留余数一般会选择key的其中几位作为散列值作为散列地址，避免了直接定址的问题，但是随机性随之降低。

如果事先知道key的大概范围，可以分析出key的若干随机性较高的位作为散列地址，这就是数学分析法。缺点也很明显，我们一般无法知道key的取值分布。

比较先进的方法是折叠法和平方取中法。折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。平方取中通过将key平方后取中间几位作为散列地址。这两种方法都能较好的利用key的随机性。

冲突处理

再好的函数也有可能冲突，对于不能避免的的冲突，就需要处理这些情况。这里简单介绍三种比较常见的冲突处理方法。

首先是链地址法，即将散列到同一个存储位置的所有元素保存在一个链表中。这种方式实现简单，而且不会占用其他散列地址的位置。一种可能的实现是类似栈的实现，即头插链表。新元素被插入到表的前端还是后端完全取决于怎样方便。

链地址法带来的问题是占用空间，如果散列表占用空间有限，就可以使用一种再散列的方法。即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法增加了散列地址的计算时间，但是一般而言不会出现数据“聚集”的问题。

最后一种便是开放定址法。开放定址又可以有线性探测法、伪随机探测和平方探测三种。

HashMap中的散列函数

HashMap解决冲突的方法相对于理论方法又有了一些改进，例如它的散列函数结合了折叠法和除留余数法作为扰动函数。HashMap的余数设计的非常巧妙，hashmap要求容器的容量capacity必须为2的幂并且余数选取了capacity - 1，这样做的好处就是能对散列操作随容量大小进行动态改变，增大了随机性，这也是为什么hashMap可能在插入过程中修改元素顺序的原因。

扰动和

HashMap的散列值是基于key的散列值生成的。理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现冲突的。但问题是一个40亿长度的数组，内存是放不下的。HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。源码中模运算是在这个indexFor函数里完成的。

static int indexFor(int h, int length) {
    return h & (length-1);
}

定位操作很简单，因为HashMap规定length一定是2的幂，所以对于2的n次方的length，length-1的二进制一定是n个1，正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做&操作如下，结果就是截取了最低的四位值。但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，冲突也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就会出现极端情况。“扰动函数”的价值就体现在这里，右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

哈希

JDK7以前的散列

hash为了防止只有 hashCode() 的低 bit 位参与散列容易碰撞，也采用了位移异或，只不过不是高低16bit，而是多次位移异或。

JKD7的 hash 中存在一个开关：hashSeed。开关打开(hashSeed不为0)的时候，对 String 类型的key 采用sun.misc.Hashing.stringHash32的 hash 算法；对非 String 类型的 key，多一次和hashSeed的异或，也可以一定程度上减少碰撞的概率。

hashSeed的值通过Holder类中的一个参数jdk.map.althashing.threshold设置，该参数默认值-1代表禁用替代hash算法，0是一直使用替代hash算法。

Oracle建议该值设置为512。如果Map容量大于512个映射，那么hashSeed会改为1，即使用替代hash算法。替代hash算法主要作用是减少冲突概率。

stringHash32()的算法基于MurMur哈希，其中hashSeed的产生使用了Romdum.nextInt()实现。Rondom.nextInt()使用AtomicLong，它的操作是CAS的（Compare And Swap）。这个CAS操作当有多个CPU核心时，会存在许多性能问题。JDK8使用红黑树解决极端冲突，已经将hashSeed和jdk.map.althashing.threshold参数移除

HashMap对冲突的处理

扩容处理冲突

再好的散列函数也有可能冲突，随着容器中键值对数量增多，定长的散列表无可避免的会造成冲突，例如采用链地址处理冲突的hashMap，容量为16，要存储17个键值对，就肯定会有冲突，所以除了传统的链地址法以外，HashMap一个处理冲突的最重要的措施之一就是扩容。第一次put元素时，HashMap就会进行扩容，在此之前都是空数组。此后，当HashMap存储的键值对的数量和容器容量的比值超过了负载因子，就会触发扩容。默认的负载因子是0.75，如果无法再扩容了，就会增大负载因子。负载因子的设计也需要考量，如果loadFactor太大会导致冲突严重，插入查找效率退化为O(N)，如果太小又会频繁扩容，浪费空间。hashMap并不建议自定义修改这个0.75。

当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值---即当前数组的长度乘以加载因子的值的时候，就会把数组增大到原来的两倍（indexFor进行与操作时多一个位）。首先会判断容量是否已经达到最大值，如果达到最大值，由于无法再进行扩容，所以不会扩容，只会增大负载因子。扩容操作会先初始化一个新的数组，然后将数据转移，这期间会对数据进行重散列。因为桶的数量一定是二的幂，所以元素重新哈希后要么在原位置，要么在原位置加上oldCapacity。如果原数据的key的哈希值增加的高位为0，resize 后 index 不变。

增加高位为0

如果增加的高位为1，resize 后 index 增加 oldCap。

增加高位为1

这个设计的巧妙之处在于，节省了一部分重新计算hash的时间，同时新增的一位为0或1的概率可以认为是均等的，所以在resize 的过程中就将原来碰撞的节点又均匀分布到了两个bucket里。

另外，JDK7和JDK8的扩容是不一样的，JDK7扩容会倒置原来的链表顺序，由于HashMap并不线程安全，所以如果有两个线程同时去尝试扩容，在倒置链表的过程中可能会把另一个线程扩容完成的数据抢过来，产生数据丢失并且死循环，在get操作的时候就有可能让cpu空转最终系统gg。JDK8对扩容进行了优化，就是刚才说的优化rehash操作，key的hashcode在扰动后，如果对新余数取余的最高位为0，rehash后位置不变，换句话说就是元素重新散列后要么在原位置，要么在原位置加上oldCapacity，这样做

链地址法

hashMap使用头插链表来进行put元素，找到链表尾部的时间复杂度是O(n)，或者需要使用额外的内存地址来保存链表尾部的位置。头插法可以节省插入耗时。

Java开发规范和HashMap元素重复问题

Java有一条开发规范，就是hashCode和equals必须一起重写。Java对于eqauls方法和hashCode方法是这样规定的：

接下来简单说下，如果不遵守这个规范，对于HashMap来说会造成什么问题。

HashMap的映射地点是通过对象的hashcode来计算的，对象的hashcode又是可以重写的，如果有人把一个对象的hashcode方法重写了返回一个1那么无论怎么样都会冲突，JDK8做了一些优化，碰撞的链表长度达到一个阈 yu 值TREEIFY_THRESHOLD（默认8)，并且总的键值对数量大于64后，会把该链表转变成红黑树结构，但是并不能完全解决这种极端的问题。

另外HashMap的get方法通过调用hashcode方法找到数组下标，但是判断链表有无重复节点却使用equals方法。如果重写equals方法的同时没有重写hashcode，就会引发一些莫名其妙的错误。

最后

个人总结，错漏难免，欢迎指正。

上一篇下一篇

猜你喜欢

热点阅读