花 5 分钟手写一个简单的 HashMap,搞定挑剔面试官
前言
今天去面试啊,聊得差不多的时候面试官突然问我会手写 HashMap 吗?这我哪能怂啊,好死不死的面试之前我还真手写过一个简单的 HashMap,所以我不过花了 5 分钟便弄出来了,面试官直呼内行。
相信大家关于 HashMap 的面试题刷的也不少了,源码应该也看了很多遍,大部分人可以说是非常熟悉了,但是如果面试官突然给你们整这么一手,我相信很多人还是会表示懵逼的。所以今天给大伙捋一捋,掌握手写 HashMap 之后都给我去手撕面试官。
除了 hashmap 之外我还整理了很多经典面试题,做成了一本 PDF,内容不多,但全是干货,需要的朋友可以点击这里领取>>互联网公司Java面试核心知识
HashMap 是 Java 中一中非常常用的数据结构,也基本是面试中的“必考题”。它实现了基于“K-V”形式的键值对的高效存取。JDK1.7 之前,HashMap 是基于数组+链表实现的,1.8 以后,HashMap 的底层实现中加入了红黑树用于提升查找效率。
HashMap 根据存入的键值对中的 key 计算对应的 index,也就是它在数组中的存储位置。当发生哈希冲突时,即不同的 key 计算出了相同的 index,HashMap 就会在对应位置生成链表。当链表的长度超过 8 时,链表就会转化为红黑树。
手写 HashMap 之前,我们讨论一个小问题:当我们在 HashMap 中根据 key 查找 value 时,在数组、链表、红黑树三种情况下,平均要做多少次比较?
在数组中查找时,我们可以通过 key 的 hashcode 直接计算它在数组中的位置,比较次数为 1
在链表中查找时,根据 next 引用依次比较各个节点的 key,长度为 n 的链表节点平均比较次数为 n/2
在红黑树中查找时,由于红黑树的特性,节点数为 n 的红黑树平均比较次数为 log(n)
前面我们提到,链表长度超过 8 时树化(TREEIFY),正是因为 n=8,就是 log(n) < n/2 的阈值。而 n<6 时,log(n) > n/2,红黑树解除树化(UNTREEIFY)。另外我们可以看到,想要提高 HashMap 的效率,最重要的就是尽量避免生成链表,或者说尽量减少链表的长度,避免哈希冲突,降低 key 的比较次数。
手写 HashMap
定义一个 Map 接口
也可以使用 Java 中的java.util.Map
然后编写一个 MyHashMap 类,实现这个接口,并实现里面的方法。
成员变量
我们参照 HashMap 设置一个默认的容量 capacity 和默认的加载因子 loadFactor,table 就是底层数组,Entry 类保存了"K-V"数据,next 字段表明它可能会是一个链表节点。
构造方法
这里的upperMinPowerOf2
的作用是获取大于 capacity 的最小的 2 次幂。在 HashMap 中,开发者采用了更精妙的位运算的方式完成了这个功能,效率比这种方式要更高。
为什么 HashMap 的 capacity 一定要是 2 次幂呢?这是为了方便 HashMap 中的数组扩容时已存在元素的重新哈希(rehash)考虑的。
put 方法
put 方法中,我们通过传入的 K-V 值构建一个 Entry 对象,然后判断它应该被放在数组的那个位置。回想我们之前的论断:
想要提高 HashMap 的效率,最重要的就是尽量避免生成链表,或者说尽量减少链表的长度
想要达到这一点,我们需要 Entry 对象尽可能均匀地散布在数组 table 中,且 index 不能超过 table 的长度,很明显,取模运算很符合我们的需求int index = k.hashCode() % table.length
。关于这一点,HashMap 中也使用了一种效率更高的方法——通过 &运算完成 key 的散列,有兴趣的同学可以查看 HashMap 的源码。
如果 table[index]处已存在元素,说明将要形成链表。我们首先遍历这个链表(长度为 1 也视作链表),如果存在 key 与我们存入的 key 相等,则替换并返回旧值;如果不存在,则将新节点插入链表。插入链表又有两种做法:头插法
和尾插法
。如果使用尾插法,我们需要遍历这个链表,将新节点插入末尾;如果使用头插法,我们只需要将 table[index]的引用指向新节点,然后将新节点的 next 引用指向原来 table[index]位置的节点即可,这也是 HashMap 中的做法。
如果 table[index]处为空,将新的 Entry 对象直接插入即可。
get 方法
调用 get 方法时,我们根据 key 的 hashcode 计算它对应的 index,然后直接去 table 中的对应位置查找即可,如果有链表就遍历。
remove 方法
移除某个节点时,如果该 key 对应的 index 处没有形成链表,那么直接置为 null。如果存在链表,我们需要将目标节点的前驱节点的 next 引用指向目标节点的后继节点。由于我们的 Entry 节点没有 previous 引用,因此我们要基于目标节点的前驱节点进行操作,即:
current 代表我们要删除的节点的前驱节点。
还有一些简单的 size()、isEmpty()等方法都很简单,这里就不再赘述。现在,我们自定义的 MyHashMap 基本可以使用了。
最后
关于 HashMap 的实现,还有几点我们没有解决:
扩容问题。在 HashMap 中,当存储的元素数量超过阈值(threshold = capacity * loadFactor)时,HashMap 就会发生扩容(resize),然后将内部的所有元素进行 rehash,使 hash 冲突尽可能减少。在我们的 MyHashMap 中,虽然定义了加载因子,但是并没有使用它,capacity 是固定的,虽然由于链表的存在,仍然可以一直存入数据,但是数据量增大时,查询效率将急剧下降。
树化问题(treeify)。我们之前讲过,链表节点数量超过 8 时,为了更高的查询效率,链表将转化为红黑树。但是我们的代码中并没有实现这个功能。
null 值的判断。HashMap 中是允许存 null 值的 key 的,key 为 null 时,HashMap 中的 hash()方法会固定返回 0,即 key 为 null 的值固定存在 table[0]处。这个实现起来很简单,不实现的情况下 MyHashMap 中如果存入 null 值会直接报
NullPointerException
异常。一些其他问题。
相信大家自己完成了对 HashMap 的实现之后,对它的原理一定会有更深刻的认识,本文如果有错误或是不严谨的地方也欢迎大家指出。上述的问题我们接下来再逐步解决。
往期热文:
end
版权声明: 本文为 InfoQ 作者【北游学Java】的原创文章。
原文链接:【http://xie.infoq.cn/article/cd26eccc473569132ed846276】。文章转载请联系作者。
评论