Java集合之HashMap源码分析

以下源码均为jdk1.7

HashMap概述

HashMap是基于哈希表的Map接口的非同步实现. 提供所有可选的映射操作, 并允许使用null值和null健. 此类不保证映射的顺序.

需要注意的是: HashMap不是同步的.

哈希表

哈希表定义: 哈希表是一种根据关键码去寻找值的数据映射结构, 该结构通过把关键码映射的位置去寻找存放值的地方.

举个例子, 最典型的例子就是字典, 如果想要在字典中查找"按"字, 通常会根据拼音 an 去查找拼音索引(当然也可以是偏旁索引), 然后找到 ti 在字典中的位置, 得到第一个拼音为 an 的字 "安". 这个过程就是键码映射, 即 通过 key 查找 f(key). 其中 key为关键字, f()是哈希函数, 哈希函数的结果就是哈希值.

哈希冲突: 那么问题来了, 我们要查找的是"按",而不是"安", 但他们的拼音都是一样的. 通过关键字 an "按"和"安"可以映射到一样的字典页码4的位置, 这就是哈希冲突(也叫哈希碰撞), 在公式上表达就是 key1 != key2, 但f(key1)=f(key2).

key 为值, f(key)计算得出数组中存储地址, 这样就会出现两个元素的地址相同的情况. 这时, 哈希函数的设计就至关重要了, 好的哈希函数会尽可能的保证 计算简单和散列地址分布均匀, 但是, 数组是一个连续的固定长度的内存空间, 再好的哈希函数也不能保证得到的存储地址绝不发生冲突.

哈希冲突的解决方案有多种: 开放定址法(发生冲突, 寻找下一个), 再散列函数法, 链地址法.

HashMap就是采用了链地址发, 也就是 数组+链表 的方式.

HashMap的实现原理

最基本的数据结构有两种: 数组和指针, HashMap就是通过这两个数据结构实现的, 是数组和链表的结合体.

从图中可以看出, HashMap底层是一个数组结构, 数组中的每一项是一个链表. 当新建HashMap时, 会初始化一个数组.

HashMap的主干是一个Entry数组.

Entry是一个静态内部类, 包含 key-value.

HashMap存储的整体结构如下:

简单说, HashMap有数组+链表组成, 数组是HashMap的主体, 链表是为了解决哈希冲突而存在的, 如果定位到数组位置不含链表(当前entry的next指向null), 那么对于查找,添加等操作很快, 仅需一次寻址即可; 如果定位到的数组包含链表, 那么添加操作就要遍历链表, 然后通过key的equals方法进行逐一对比, 存在即覆盖, 不存在则新增, 而查找操作也需遍历链表.

所以, 性能考虑, HashMap中的链表出现越少, 性能越好.

HasmMap几个重要的字段:

HashMap的构造函数:

从上面代码中可以看出, 在常规构造器中, 没有为数组 table 分配内存空间(有个参数为map的构造器除外), 而是在执行 put操作时才真正构建table数组

再来看 inflateTable()方法源码:

重量级角色, 哈希函数出场:

indexFor()函数实现如下:

h&(length - 1)保证获取的index一定在数组的范围内, 例如: 容量为16, length-1=15, h=18, 进行计算为:

得出index=2.

故而, 最终存储位置的确定为如下流程:

最后看下 addEntry 的实现:

通过 addEntry 的代码可以看出, 当发生哈希冲突并且size大于阈值时, 需要进行数组扩容, 扩容时, 需要新建一个长度为之前2倍的新数组, 最后将当前的Entry数组中元素全部传过去, 扩容后的新数组长度为之前的2倍, 所以扩容相对来说是一个耗资源的操作.

下面看get方法就简单得多了:

然后是getEntry()源码:

可以看出, get方法的实现相当简单, 流程为: key(hashcode)-->hash-->indexFor-->最终索引位置, 找到对应位置table[i], 在查看是否有链表, 遍历链表, 通过key的equals方法比对查找对应的记录.

在getEntry方法中, 定位到数组位置之后遍历链表的时候, e.hash==hash这个判断是否有必要. 试想如下场景, 如果传入的key对象重写了equals方法却没有重写hashCode, 而恰巧此对象定位到这个数组位置, 如果仅仅用equals判断可能是相等的, 但其hashCode和当前对象不一致, 这种情况, 根据Object的hashCode的约定, 不能返回当前对象, 而应该返回null.

重写equals方法要同时重写hashCode方法

为什么重写equals时也要同时重写hashCode? 下面举个小例子:

实际输出结果:

结果: null

现在我们已经对HashMap的原理有了一定了解, 这个结果就不难理解了. 尽管我们在进行get和put操作的时候, 使用的key从逻辑上讲是等值的, 但由于没有重写hashCode方法, 在进行put操作时: key(hashcod1)-->hash-->indexFor-->最终索引位置; 而通过key去除value时: key(hashcode2)-->hash-->indexFor-->最终索引位置, 由于hashcode1和hashcode2不相等, 最终得出的数组索引页不一样而返回null(也可能碰巧定位到了一个数组位置, 但是也会判断其entry的hash值是否相等, 上面get方法中有提到)

所以, 在重写equals方法时, 必须注意重写hashCode方法, 同时还要保证equals判断相等的两个对象, 调用hashCode方法要返回同样的整数值, 而equals判断不相等的两个对象, 其hashCode可以相同, 只是会发生哈希冲突, 应该尽量避免.

HashMap的遍历 总结

HashMap底层将key-value当成一个整体处理, 这个整体就是Entry对象. HashMap底层采用一个Entry[]数组来保存所有的key-value对, 当需要存储一个Entry对象时, 会根据hash算法来决定其在数组中的位置, 再根据equals方法决定其在该数组位置上的链表中的存储位置; 当需要取出一个Entry时, 也会根据hash算法找到其在数组中的存储位置, 再根据equals方法从该位置上的链表中取出该Entry.