一道面试题看 HashMap 的存储方式

我们公司招人喜欢问算法题和一些基础知识。今天我们一个面试官在面试候选人之前在办公室对我们说他准备问一个这样的问题:

在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型。放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么?

我们办公室几个人答案都不一致,有的说返回null,有的说能正常返回value。但不论答案是什么都没有确凿的理由。我觉得这个问题挺有意思的,就写了代码测试。结果是返回null。需要说明的是我们自定义的类重写了 hashCode 方法。我想这个结果还是有点意外的,因为我们知道 HashMap 存放的是引用类型,我们在外面把 key 更新了,那也就是说 HashMap 里面的 key 也更新了,也就是这个 key 的 hashCode 返回值也会发生变化。这个时候 key 的 hashCode 和 HashMap 对于元素的 hashCode 肯定一样,equals也肯定返回true,因为本来就是同一个对象,那为什么不能返回正确的值呢?

先来看看一段测试代码:

先解释一下测试代码做到事。定义了一个person类,就两个属性。重写了 hashCode 方法,还有一套geter和seter,没什么特别。测试类里面先创建了三个person对象作为 key 。打印各个 key 的 hashCode 值。然后三个元素放到 HashMap ,接着更新其中一个 key 的name属性,最后去取这个 key 的value。

输出:

从输出我们可以知道, key 更新后 hashCode 确实更新了。而且 HashMap 里面的对象就是我们原来的对象。最后的结果是null。

我们来看一下 HashMap 的get方法源代码:

可以看到先取得了一个table,这个table实际上是个数组。然后在table里面找对应 key 的value。找的标准就是hash等于传入参数的hash, 并且满足另外两个条件之一:k = e.key,也就是说他们是同一个对象,或者传入的 key 的equal目标的 key 。我们的问题出在那个hash(key.hashCode()),可以看到 HashMap 在存储元素时是把 key 的 hashCode 再做了一次hash。得到的hash将最终作为元素存储位置的依据。对应到我们的情况:第一次存储时,hash函数采用key.hashCode作为参数得到了一个值,然后根据这个值把元素存到了某个位置。

当我们再去取元素的时候,key.hashCode的值已经出现了变化,所以这里的hash函数结果也发生了变化,所以当它尝试去获得这个 key 的存储位置时就不能得到正确的值,导致最终找不到目标元素。要想能正确返回,很简单,把Person类的 hashCode 方法改一下,让它的 hashCode 不依赖我们要修改的属性,但实际开发中肯定不能这么干,我们总是希望当两个对象的属性不完全相同时能返回不同的 hashCode 值。所以结论就是当把对象放到 HashMap 后,不要去修改 key 的属性。

以上都是很基础的东西,但或许我们很多时候都没注意到,了解这些基础可以避免一些很诡异的bug。纯属抛砖引玉,如有谬误请海涵和指出。

2 12 收藏 25 评论

关于作者:梧桐

(新浪微博:@jakiewoo_vp9) 个人主页 · 我的文章 · 13

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 路过的   2014/05/17

    太小儿科了吧~~那么多答不上来的人是怎么招进来的~~

  • farewellwho   2014/05/17

    虽然一个很简单的问题,但是作者探讨的很深入,也拿出来和大家分享了,赞一个!
    所以“HashMap 在存储元素时是把 key 的 hashCode 再做了一次hash”这句话足够解释所有问题了。

    • mozila   2014/05/29

      关键点不是“HashMap 在存储元素时是把 key 的 hashCode 再做了一次hash”,而是“第一次存储时,hash函数采用key.hashCode作为参数得到了一个值,然后根据这个值把元素存到了某个位置”。HashMap的key是记录了key的值,而不是引用

  • cris   2014/05/17

    注释掉重写的hashCode()方法,Final Result:p2。
    这是什么原因?

    • cris   2014/05/17

      不好意思,没仔细文章的结尾。想了一下,应该是因为在重写的hashCode()方法对name调用了hashCode()方法,所以对象的hashCode就改变了,导致了结果为Final Result:null。不知道这样解释是否正确,新手一个,请高手指教。

  • cs   2014/05/17

    叼。。。

  • will   2014/05/17

    看来我能进你们公司啊。这问题只要看过hashmap的源码,就肯定能答得出来。

  • haxshx   2014/05/18

    其实这么选hashCode就不正常吧,
    一般hashcode要取在不会更新/重复的主键上才对吧。
    还不如直接考hashmap实现原理,更大气直接一点。

  • 一心悟   2014/05/18

    不错

  • Moshoujingli   2014/05/19

    在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型。放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么?

    我刚开始看到这个问题没意识到提到的HashMap 是说Java的HashMap ,所以我觉得是null和正确值或者错误值都可能。因为HashMap 实现原理是使用key来确定value的存放位置,那么既然key改变了,那么计算出来的存放位置也可能变了,返回null(也可能不变,恰好hash冲突,那么就请参照后面,看此实现是否检查了两key相等,不检查就可能返回正确值);那个位置上如果有value的话,视那个实现有没有检查那个位置上只有一个value的时候key是否相等(一般都检查吧,不检查的话可能就返回个错误值了。当然也可能碰巧这个错key的value和目标value一个,那就不算了)从而返回null(检查且不等),错误值(检查且相等,这个看那个自定义类型的等于的实现了)。

    不过既然说了是Java里面的,JDKxxx的话,就没那么多可能了lol,不过还是得具体看自定义类型的HashCode实现和equal实现。

    • Moshoujingli   2014/05/19

      补充一下,恰好哈希冲突那个情况,就是返回正确值了。。。

      • njbam   2014/05/19

        hashMap 除了处理hash冲突之外还会比较 key 值是否相等,key改变了,就算发生hash碰撞也不会出来数据吧。

        • Moshoujingli   2014/06/05

          嗯,是,正常而言都是比较的。但是如果是一些特别情况(包括实现的人忘了,以及我前些天解的BUG,某两个内容不同文件的sha1竟然一样(这也算是哈希碰撞了吧)导致之后这个类似于hashmap的系统出现了一些奇葩问题)还是会有类似的问题。

          如果说规定好是哪个东西的HashMap实现这事就好说了,不然,确实各种边界条件影响更大吧。。。

  • Edward Shen   2014/05/19

    倒! 有人不知道这个吗?

  • LookingID   2014/05/19

    没说到点子上,看一下HashMap的实现就清楚了,着重看indexFor()方法,在put时用key的hash值确定存储位置,并保存该位置到一个Entry数组对象,注意这里存的是数组地址。由于key类的实现中override了hashCode方法,导致当key被改变之后,hash值也被改变,因此在get中,indexFor通过新hash值去找内存地址,自然找不到存在原地址的值。

  • 自己曾学过JAVA 但没有坚持,好想有人教我。。。可能要培训去了

  • 我有两处疑惑,首先说明本人没有学习过java:
    1、“并且满足另外两个条件之一:k = e.key,也就是说他们是同一个对象,或者传入的 key 的equal目标的 key ”根据你文中的这句话,我并不能理解get()里面的逻辑是怎么实现的。按着你的说明如果是正常情况(即没有修改任何对象),这句话以后它没有获得hash值,岂不是所有里面存在的元素都会将hash值再hash一次?是怎么实现查找的?
    2、我专门搜索了一下hashCode();这个函数是获取key的物理地址,物理地址就是它在内存中的实际位置。并不是已有的hash值(如果这种解释正确那么这个函数的查找逻辑就可以理解了)。

  • 总结一下:

    首先,问题中“其中key为某个我们自定义的类型,在外部把某一个 key 的属性进行更改”,这并不是HashMap能否再次取得元素的关键,关键在于“自定义的类型”中的hashCode方法和equals是怎么写的, 因为HashMap的put和get机制都和这两个方法息息相关, 如果“在外部把某一个 key 的属性进行更改”中的那个属性对hashCode和equals方法的返回值并无影响,必定可以再次从HashMap取得该元素。

    第二, 之所以取出null的原因在于:我们把包寄存在沃尔玛了,然后跑去家乐福取。。。我们put元素的时候hashCode方法返回值是xxx,HashMap根据xxx去找个地方放我们的元素;然后我们在外部改变了该元素属性,导致其hashCode方法计算的哈希值变为了yyy, HashMap再根据这个yyy去找个地方取我们的元素, 当然找不到了

    第三, 即使恰好HashMap分别根据xxx和yyy找的那个地方是同一个地方, 元素也取不回来了, 因为HashMap还会比较元素的hash值:
    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    return e.value;

    第四,以作者的代码为背景条件,个人觉得还并不是100%的几率都会取得null。 文中代码覆盖了hashCode方法,以字符串name的hashCode拼接上height作为Person实例的hashCode。 假设有个Person,名字是XYZABC身高170,然后把他put进HashMap中, 然后你在外部把他改名叫做ASDFGH了, 但是能保证"XYZABC".hashCode和"ASDFGH".hashCode一定是不一样的吗? 虽然概率小,但如果恰好

    • 但如果恰好String的hash冲突了, 那么还是可能成功取回这个元素, 因为put和get是用的同一个hash值。

  • criszhao   2014/09/10

    好弱的公司。。

  • blakebu   2015/01/08

    返回NULL 应该是因为entry中存储的hash值是在你首次put的时候根据key确定的 这个hash值不会随着key指向对象的改变而去修改entry中的hash值 这样就导致了这个entry 基本是不可能被再次取到 因为 entry中的key改变了但是key对应的hash确没有改变

  • Fine   2015/06/15

    如果不覆盖hashCode方法一定能拿到原来的元素,因为Object里的hashCode方法返回的是对象地址。如果覆盖了hashCode方法能不能拿到原来的对象就要看重写后的hashCode方法和对象的equals方法了。

跳到底部
返回顶部