HashMap 实现原理及源码分析
哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如 memcached)的核心其实就是在内存中维护一张大的哈希表,而 HashMap 的实现原理也常常出现在各类的面试题中,重要性可见一斑。本文会对 java 集合框架中的对应实现 HashMap 的实现原理进行讲解,然后会对 JDK7 的 HashMap 源码进行分析。
一、什么是哈希表
在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能
数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为 O (1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为 O (n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为 O (logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为 O (n)
线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为 O (1),而查找操作需要遍历链表逐一进行比对,复杂度为 O (n)
二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为 O (logn)。
哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为 O (1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶 O (1) 的。 我们知道,数据结构的物理存储结构只有两种:
顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。 比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。
存储位置 = f (关键字) 其中,这个函数 f 一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:
查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。
哈希冲突 然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而 HashMap 即是采用了链地址法,也就是数组 + 链表的方式,
二、HashMap 实现原理
HashMap 的主干是一个 Entry 数组。Entry 是 HashMap 的基本组成单元,每一个 Entry 包含一个 key-value 键值对。
1 | //HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂,至于为什么这么做,后面会有详细分析。 |
Entry 是 HashMap 中的一个静态内部类。代码如下
1 | static class Entry<K,V> implements Map.Entry<K,V> { |
所以,HashMap 的整体结构如下
简单来说,HashMap 由数组 + 链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前 entry 的 next 指向 null), 那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度依然为 O (1),因为最新的 Entry 会插入链表头部,急需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过 key 对象的 equals 方法逐一比对查找。所以,性能考虑,HashMap 中的链表出现越少,性能才会越好。
其他几个重要字段
1 | //实际存储的key-value键值对的个数 |
HashMap 有 4 个构造器,其他构造器如果用户没有传入 initialCapacity 和 loadFactor 这两个参数,会使用默认值 initialCapacity 默认为 16,loadFactory 默认为 0.75 我们看下其中一个
1 | public HashMap(int initialCapacity, float loadFactor) { |
从上面这段代码我们可以看出,在常规构造器中,没有为数组 table 分配内存空间(有一个入参为指定 Map 的构造器例外),而是在执行 put 操作的时候才真正构建 table 数组 OK, 接下来我们来看看 put 操作的实现吧
1 | public V put(K key, V value) { |
先来看看 inflateTable 这个方法
1 | private void inflateTable(int toSize) { |
inflateTable 这个方法用于为主干数组 table 在内存中分配存储空间,通过 roundUpToPowerOf2 (toSize) 可以确保 capacity 为大于或等于 toSize 的最接近 toSize 的二次幂,比如 toSize=13, 则 capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
1 | private static int roundUpToPowerOf2(int number) { |
roundUpToPowerOf2 中的这段处理使得数组长度一定为 2 的次幂,Integer.highestOneBit 是用来获取最左边的 bit(其他 bit 位为 0)所代表的数值. hash 函数
1 | //这是一个神奇的函数,用了很多的异或,移位等运算,对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀 |
以上 hash 函数计算出的值,通过 indexFor 进一步处理来获取实际的存储位置
1 | /** |
h&(length-1)保证获取的 index 一定在数组范围内,举个例子,默认容量 16,length-1=15,h=18, 转换成二进制计算为
1 | 1 0 0 1 0 |
最终计算出的 index=2。有些版本的对于此处的计算会使用 取模运算,也能保证 index 一定在数组范围内,不过位运算对计算机来说,性能更高一些(HashMap 中有大量位运算) 所以最终存储位置的确定流程是这样的:
再来看看 addEntry 的实现:
1 | void addEntry(int hash, K key, V value, int bucketIndex) { |
通过以上代码能够得知,当发生哈希冲突并且 size 大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组 2 倍的新的数组,然后将当前的 Entry 数组中的元素全部传输过去,扩容后的新数组长度为之前的 2 倍,所以扩容相对来说是个耗资源的操作。
三、为何 HashMap 的数组长度一定是 2 的次幂?
我们来继续看上面提到的 resize 方法
1 | void resize(int newCapacity) { |
如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index 也可能会发生变化,需要重新计算 index,我们先来看看 transfer 这个方法
1 | void transfer(Entry[] newTable, boolean rehash) { |
这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过 对 key 值的 hashcode 进行 hash 扰乱运算后,再通过和 length-1 进行位运算得到最终数组索引位置。 hashMap 的数组长度一定保持 2 的次幂,比如 16 的二进制表示为 10000,那么 length-1 就是 15,二进制为 01111,同理扩容后的数组长度为 32,二进制表示为 100000,length-1 为 31,二进制表示为 011111。从下图可以我们也能看到这样会保证低位全为 1,而扩容后只有一位差异,也就是多出了最左位的 1,这样在通过 h&(length-1) 的时候,只要 h 对应的最左边的那一个差异位为 0,就能保证得到的新的数组索引和老数组索引一致 (大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。
还有,数组长度保持 2 的次幂,length-1 的低位都为 1,会使得获得的数组索引 index 更加均匀,比如:
我们看到,上面的 & 运算,高位是不会对结果产生影响的(hash 函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位 bit,如果低位全部为 1,那么对于 h 低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到 index=21 这个存储位置,h 的低位只有这一种组合。这也是数组长度设计为必须为 2 的次幂的原因。
如果不是 2 的次幂,也就是低位不是全为 1 此时,要使得 index=21,h 的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index 对应的这个 bit 位无论如何不会等于 1 了,而对应的那些数组位置也就被白白浪费了。 get 方法
1 | public V get(Object key) { |
get 方法通过 key 值返回对应 value,如果 key 为 null,直接去 table [0] 处检索。我们再看一下 getEntry 这个方法
1 | final Entry<K,V> getEntry(Object key) { |
可以看出,get 方法的实现相对简单,key (hashcode)–>hash–>indexFor–> 最终索引位置,找到对应位置 table [i],再查看是否有链表,遍历链表,通过 key 的 equals 方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash 这个判断没必要,仅通过 equals 判断就可以。其实不然,试想一下,如果传入的 key 对象重写了 equals 方法却没有重写 hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用 equals 判断可能是相等的,但其 hashCode 和当前对象不一致,这种情况,根据 Object 的 hashCode 的约定,不能返回当前对象,而应该返回 null,后面的例子会做出进一步解释。
四、重写 equals 方法需同时重写 hashCode 方法
关于 HashMap 的源码分析就介绍到这儿了,最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写 equals 时也要同时覆盖 hashcode”,我们举个小例子来看看,如果重写了 equals 而不重写 hashcode 会发生什么样的问题
1 | /** |
实际输出结果:
结果:null
如果我们已经对 HashMap 的原理有了一定了解,这个结果就不难理解了。尽管我们在进行 get 和 put 操作的时候,使用的 key 从逻辑上讲是等值的(通过 equals 比较是相等的),但由于没有重写 hashCode 方法,所以 put 操作时,key (hashcode1)–>hash–>indexFor–> 最终索引位置 ,而通过 key 取出 value 的时候 key (hashcode1)–>hash–>indexFor–> 最终索引位置,由于 hashcode1 不等于 hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值 null(也有可能碰巧定位到一个数组位置,但是也会判断其 entry 的 hash 值是否相等,上面 get 方法中有提到。) 所以,在重写 equals 的方法的时候,必须注意重写 hashCode 方法,同时还要保证通过 equals 判断相等的两个对象,调用 hashCode 方法要返回同样的整数值。而如果 equals 判断不相等的两个对象,其 hashCode 可以相同(只不过会发生哈希冲突,应尽量避免)。
五、总结
本文描述了 HashMap 的实现原理,并结合源码做了进一步的分析,也涉及到一些源码细节设计缘由,最后简单介绍了为什么重写 equals 的时候需要重写 hashCode 方法。希望本篇文章能帮助到大家,同时也欢迎讨论指正,谢谢支持!
作者: dreamcatcher-cx
出处: http://www.cnblogs.com/chengxiao/
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在页面明显位置给出原文链接。