草庐IT

java - 无法从 Sun 文档中理解哈希表的泊松部分

coder 2023-09-02 原文

我想了解 HashMap 在 Java 中是如何实现的。我决定尝试理解该类(class)的每一行(代码和注释)，显然我很快就遇到了阻力。以下片段来自 HashMap 类并讨论了泊松分布:

 Ideally, under random hashCodes, the frequency of
 nodes in bins follows a Poisson distribution
 (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 parameter of about 0.5 on average for the default resizing
 threshold of 0.75, although with a large variance because of
 resizing granularity. Ignoring variance, the expected
 occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 factorial(k)). The first values are:
 0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

我是数学方面的普通人，必须首先了解什么是泊松分布。感谢向我解释它的简单视频。

现在，即使了解了如何使用泊松计算概率，我仍然无法理解上面描述的内容。

有人可以用更简单的语言解释一下吗？如果可能的话，可以举个例子吗？这将使我的任务变得更加有趣。

最佳答案

一个 HashMap 被组织为一个基于被插入元素的 hashCode 的“桶”数组。每个桶(默认情况下)是一个元素链表。每个桶将包含很少的元素(理想情况下，最多一个)，因此查找特定元素只需要很少的搜索链表。

举个简单的例子，假设我们有一个容量为 4 且负载因子为 0.75(默认值)的 HashMap，这意味着它在调整大小之前最多可以容纳 3 个元素。元素在桶中的理想分布看起来像这样:

bucket | elements
-------+---------
     0 | Z
     1 | X
     2 |
     3 | Y

因此可以立即找到任何元素，而无需在桶内进行任何搜索。另一方面，元素分布很差会是这样的:

bucket | elements
-------+---------
     0 | 
     1 | Z -> X -> Y
     2 |
     3 |

如果所有元素碰巧散列到同一个桶中，就会发生这种情况，因此搜索元素 Y 需要向下遍历链表。

这可能看起来没什么大不了的，但是如果你有一个容量为 10,000 个元素的 HashMap，并且链表上的单个桶中有 7,500 个元素，搜索特定元素将降低到线性搜索时间 - - 这是使用 HashMap 试图避免的。

一个问题是，用于将元素分配到桶中的 hashCode 由对象本身决定，而对象的 hashCode 实现并不总是很好。如果 hashCode 不是很好，则元素会聚集在某些桶中，HashMap 的性能就会开始下降。

代码中的注释是在讨论每个桶中出现不同长度的链表的可能性。首先，它假设哈希码是随机分布的——但情况并非总是如此! -- 我认为它还假设 HashMap 中的元素数量是桶数量的 50%。在这些假设下，根据泊松分布，60.6% 的桶为空，30.3% 的桶有一个元素，7.5% 的桶有两个元素，1.2% 的桶有三个元素，依此类推。

换句话说，给定那些(理想的)假设，每个桶中的链表通常会很短。

在 JDK 8 中有一个优化，可以将链表转换为超过特定阈值大小的树，因此在最坏的情况下，性能至少会降低到 O(log n) 而不是 O(n)。问题是，应该选择什么值作为阈值？这就是本次讨论的全部内容。当前阈值 TREEIFY_THRESHOLD 为 8。同样，在这些理想假设下，具有长度为 8 的链表的桶将仅在 0.000006% 的时间内出现。所以如果我们得到一个那么长的链表，显然有些事情是不理想的!!这可能意味着，例如，正在存储的对象具有异常糟糕的 hashCode，因此 HashMap 必须从链表切换到树，以避免性能过度下降。

带有相关评论的源文件链接在这里:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java

关于java - 无法从 Sun 文档中理解哈希表的泊松部分，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20448477/

javaSunHashMap的sectionpoisson

有关java - 无法从 Sun 文档中理解哈希表的泊松部分的更多相关文章

  1. ruby-on-rails - 由于 "wkhtmltopdf"，PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中，我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  2. ruby-on-rails - 无法使用 Rails 3.2 创建插件？ - 2

    我对最新版本的Rails有疑问。我创建了一个新应用程序(railsnewMyProject)，但我没有脚本/生成，只有脚本/rails，当我输入ruby./script/railsgeneratepluginmy_plugin"Couldnotfindgeneratorplugin.".你知道如何生成插件模板吗？没有这个命令可以创建插件吗？PS:我正在使用Rails3.2.1和ruby​​1.8.7[universal-darwin11.0] 最佳答案 随着Rails3.2.0的发布，插件生成器已经被移除。查看变更日志here.现在

  3. ruby - 无法运行 Rails 2.x 应用程序 - 2

    我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby​​:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r

  4. ruby-on-rails - 无法在centos上安装therubyracer(V8和GCC出错) - 2

    我正在尝试在我的centos服务器上安装therubyracer，但遇到了麻烦。$geminstalltherubyracerBuildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingtherubyracer:ERROR:Failedtobuildgemnativeextension./usr/local/rvm/rubies/ruby-1.9.3-p125/bin/rubyextconf.rbcheckingformain()in-lpthread...yescheckingforv8.h...no***e

  5. ruby - 无法让 RSpec 工作—— 'require' : cannot load such file - 2

    我花了三天的时间用头撞墙，试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上，从现在开始，您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳

  6. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  7. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  8. ruby - 无法覆盖 irb 中的 to_s - 2

    我在pry中定义了一个函数:to_s，但我无法调用它。这个方法去哪里了，怎么调用？pry(main)>defto_spry(main)*'hello'pry(main)*endpry(main)>to_s=>"main"我的ruby版本是2.1.2看了一些答案和搜索后，我认为我得到了正确的答案:这个方法用在什么地方？在irb或pry中定义方法时，会转到Object.instance_methods[1]pry(main)>defto_s[1]pry(main)*'hello'[1]pry(main)*end=>:to_s[2]pry(main)>defhello[2]pry(main)

  9. ruby - 无法在 60 秒内获得稳定的 Firefox 连接 (127.0.0.1 :7055) - 2

    我使用的是Firefox版本36.0.1和Selenium-Webdrivergem版本2.45.0。我能够创建Firefox实例，但无法使用脚本继续进行进一步的操作无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)错误。有人能帮帮我吗？ 最佳答案 我遇到了同样的问题。降级到firefoxv33后一切正常。您可以找到旧版本here 关于ruby-无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)，我们在StackOverflow上找到一个类

  10. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

随机推荐