技术控

    今日:147| 主题:49136
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 图解HashMap和HashSet的内部工作机制

[复制链接]
难瘦 发表于 2016-10-5 07:33:58
147 2

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
HashMap 和 HashSet 内部是如何工作的?散列函数(hashing function)是什么?
   HashMap不仅是一个常用的数据结构,在面试中也是热门话题。
  Q1. HashMap 如何存储数据?
  A1. 以键/值对(key/value)形式存储。你可以使用键(key)来存、取值。
  Q2. HashMap 查询时间的复杂度是怎样的?
   A2. 是O( n ) = O(k * n)。如果 hashCode() 方法能向下面讨论的那样把数据分散到桶(bucket)中,那么平均是O(1)。
  Q3. HashMap 内部是如何存储数据的?
  A3. HashMap 使用后台数组(backing array)作为桶,并使用链表(linked list)存储键/值对。
  桶的后台数组:如下所示
   
图解HashMap和HashSet的内部工作机制-1 (function,backing,热门话题,linked,Peter)

   1)使用键(key)和值(value)将一个对象放入 map 中时,会隐式调用 hashCode() 方法,返回哈希值(hash code value),比如 123。两个不同的键能够返回一样的哈希值。良好的哈希算法(hashing algorithm)能够将数值分散开。在上面的例子中,我们假设 (“John”,01/01/1956) 的键和 (“Peter”, 01/01/1995) 的键返回相同的哈希值,都是  123

图解HashMap和HashSet的内部工作机制-2 (function,backing,热门话题,linked,Peter)

   2)当返回一个 hashCode,例如是 123,初始的 HashMap 容量为 10,它如何知道存储到后台数组(backing array)的哪个索引(index)呢?HashMap 内部会调用 hash(int ) 和 indexFor(int h, int length) 方法。这被称为 哈希 函数(hashing function)。
  简要解释下这个函数:
  [code]hashCode() % capacity

123 % 10 = 3
456 % 10 = 6[/code]  这表示,“hashCode = 123”存储在备份数组的索引3上。
   容量为 10 的情况下,你可能得到的数字在 09 之间。
   一旦 HashMap 达到容量的 75%,也就是哈希因子(hash factor)默认值 0.75,后台数组(backing array)的容量就会加倍,发生 重散列 (rehashing)为新的 20 的容量重新分配桶。
  [code]hashCode() % capacity

123 % 20 = 3
456 % 20 = 16[/code]  上面重散列的取模方法有一个缺陷。如果 hashCode 是负数会怎样?负索引可不是你想要的。因此,一个改进的哈希公式会移出符号位,然后再用取模(即 %)运算符计算剩余部分。
  [code](123  & 0x7FFFFFFF) % 20 = 3
(456 & 0x7FFFFFFF) % 20 = 16[/code]  这确保你得到的索引值为正数。如果你查看 Java 8 的 HashMap 源码,它的实现使用以下方法:
   a).通过只抽取重要的低位,来防止不良离散值(poorer hashes)。
  [code]static int hash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
}[/code]   b).根据 哈希码hashCode )和 容量capacity ),来决定索引(index)。
  [code]static int indexFor(int h, int length) {
     return h & (length-1);
}[/code]  实际的名称值对(name value pairs)作为一个键/值对存储在 LinkedList 中。
   如上图所示,键/值对以链表形式存储。两个不同的键可以产生一样的 hashCode,例如123,并存储在同一个 bucket 中,理解这点至关重要。例如,上面例子中的 “John, 01/01/1956” 和 “Peter, 01/01/1995“ 。你如何只检索 “John, 01/01/1956” 呢?此时你的 key 所属类的 equals() 方法会被调用。它遍历 bucket 为 “123” 的 LinkedList 中的每个条目,使用 equals() 方法找到并检索出键为 “John, 01/01/1956” 的条目。这就是在你的类中实现 hashCode()equals() 方法重要性的原因。如果你使用一个现有的包装类,如 Integer 或 String 作为键,它们已经实现了这两个方法。如果你使用自己写的类作为键,如 “John, 01/01/1956” 这样含有名字和出生日期属性的“MyKey”,你有责任正确地实现这些方法。
  Q5. 为什么恰当地设置 HashMap 的初始容量(initial capacity)是最佳实践?
   A5. 这样可以减少 重散列 的发生。
  Q6. HashSet 内部如何存储数据?
  A6. HashSet 内部使用 HashMap 。它将元素存储为键和值。(译者注:HashSet 把存储的值作为 key)
  Q7. 为 Object 实现了一个糟糕的 hashcode() 会有什么影响?
   A7. 不同的对象调用 hashCode() 方法应该返回不同的值。如果不同的对象返回相同的值,会导致更多的键/值对存储在同一个 bucket 中。这会 降低 HashMap 和 HashSet 的 性能
   原文链接: Arulkumaran Kumaraswamipillai 翻译:ImportNew.com -齐帜背单词吧
译文链接:[]
友荐云推荐




上一篇:The week in .NET – On .NET on Cecil – NAudio – SpeechCentral – Hand of Fate ...
下一篇:This Week in Rust 150
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

胡志强 发表于 2016-10-15 13:29:02
有空一起交流一下
回复 支持 反对

使用道具 举报

旦宅恩 发表于 2016-11-3 13:19:13
不错,顶一个!
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表