草庐IT

java - 当 hashcode() 实现返回常量值时，为什么哈希表会退化为链表？

coder 2024-03-16 原文 

// The worst possible legal hash function - never use!
@Override public int hashCode() { return 42; }

It’s legal because it ensures that equal objects have the same hash code. It’s atrocious because it ensures that every object has the same hash code. Therefore, every object hashes to the same bucket, and hash tables degenerate to linked lists. Programs that should run in linear time instead run in quadratic time.

我正在尝试解决上述问题(引自第 47 页，第 9 项，Joshua Bloch 的 Effective Java)。

我的看法如下(考虑以下代码):

Map<String, String> h = new HashMap<String,String>();
h.put("key1", "value1");
h.put("key1", "value2");

第二个 h.put("key1",...) 命令发生的情况如下: 1.获取key1的hashcode 2. 获取代表上述hashcode的bucket 3. 在该桶中，对于每个对象，调用 equals 方法来查找是否存在相同的对象。

这有点快，因为首先您会找到对象的“组”(桶)，然后是实际对象。

现在，当 hashcode 实现为 ALL 对象返回相同的整数(例如上面的 42)时，那么只有一个桶，并且equals 方法需要在整个 hashmap/hashtable 中的每个对象上逐一调用。这和链表一样糟糕，因为如果对象位于链表中，那么也必须逐一比较(调用等于)每个对象。

据说，这就是哈希表退化为链表的原因吗？

(对于上面文字的冗长，我深表歉意。我的概念还不够清楚，无法更简洁地表述)

最佳答案

HashTable是一个具有映射函数(hashCode)的数组。插入数组时，您计算位置并将元素插入该位置。

但是，hashCode 并不能保证每个元素都有不同的位置，因此某些对象可能会发生冲突(具有相同的地址)并且 hashTable 必须解决它。有两种常见的方法，如何做到这一点。

独立链接

在单独的链接(在 Java 中使用)中，数组的每个索引都包含一个链表 - 因此每个桶(位置)都有无限的容量。因此，如果您的 hashCode 仅返回一个值，则您只使用了一个喜欢的列表 => hashTable 是一个链表。

线性探测

第二种方法是线性探测。在线性探测中，内部数组实际上是普通的元素数组。当您发现该位置已被占用时，您将遍历数组并将新元素放在第一个空位置。

所以我的 hashCode 实现为每个元素生成了常量值，你只生成了碰撞，因此你试图将所有元素放置到同一个索引中，并且因为总是被占用，你遍历所有已放置的元素并放置此结构 末尾的新元素。如果您再次阅读，您必须看到，您正在使用的只是一个不同的(您可以说是隐含的)链表实现。

为什么不这样做

你真的不应该返回常量值，因为哈希表的构建是为了提供 O(1) 搜索和插入操作的预期复杂性(因为哈希函数，它返回一个不同的地址(几乎) 每个不同的对象)。如果您只返回一个值，则实现降级为两个操作的 O(n) 链表。

关于java - 当 hashcode() 实现返回常量值时，为什么哈希表会退化为链表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7776297/

量值化为codesectionstrongjavaalgorithmequalshashcode

有关java - 当 hashcode() 实现返回常量值时，为什么哈希表会退化为链表？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  3. ruby-on-rails - 未初始化的常量 Psych::Syck (NameError) - 2

    在我的gem中，我需要yaml并且在我的本地计算机上运行良好。但是在将我的gem推送到ruby​​gems.org之后，当我尝试使用我的gem时，我收到一条错误消息=>"uninitializedconstantPsych::Syck(NameError)"谁能帮我解决这个问题？附言RubyVersion=>ruby1.9.2,GemVersion=>1.6.2,Bundlerversion=>1.0.15 最佳答案 经过几个小时的研究，我发现=>“YAML使用未维护的Syck库，而Psych使用现代的LibYAML”因此，为了解决

  4. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  5. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  6. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  7. ruby-on-rails - active_admin 目录中的常量警告重新声明 - 2

    我正在使用active_admin，我在Rails3应用程序的应用程序中有一个目录管理，其中包含模型和页面的声明。时不时地我也有一个类，当那个类有一个常量时，就像这样:classFooBAR="bar"end然后，我在每个必须在我的Rails应用程序中重新加载一些代码的请求中收到此警告:/Users/pupeno/helloworld/app/admin/billing.rb:12:warning:alreadyinitializedconstantBAR知道发生了什么以及如何避免这些警告吗？ 最佳答案 在纯Ruby中:classA

  8. ruby - ruby 中的 TOPLEVEL_BINDING 是什么？ - 2

    它不等于主线程的binding，这个toplevel作用域是什么？此作用域与主线程中的binding有何不同？>ruby-e'putsTOPLEVEL_BINDING===binding'false 最佳答案 事实是，TOPLEVEL_BINDING始终引用Binding的预定义全局实例，而Kernel#binding创建的新实例>Binding每次封装当前执行上下文。在顶层，它们都包含相同的绑定(bind)，但它们不是同一个对象，您无法使用==或===测试它们的绑定(bind)相等性。putsTOPLEVEL_BINDINGput

  9. ruby - Infinity 和 NaN 的类型是什么？ - 2

    我可以得到Infinity和NaNn=9.0/0#=>Infinityn.class#=>Floatm=0/0.0#=>NaNm.class#=>Float但是当我想直接访问Infinity或NaN时:Infinity#=>uninitializedconstantInfinity(NameError)NaN#=>uninitializedconstantNaN(NameError)什么是Infinity和NaN？它们是对象、关键字还是其他东西？ 最佳答案 您看到打印为Infinity和NaN的只是Float类的两个特殊实例的字符串

  10. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

随机推荐