jjzjj

c# - 散列过程如何在 Dictionary<TKey, TValue> 中工作

coder 2024-05-23 原文

Dictionary 中的散列过程是如何工作的？我读到使用字典可以更快地查找。但是没看懂怎么办？散列和映射到索引是如何发生的？找不到任何好的引用。

编辑: 如何从哈希函数的结果中得到对象实际存储的内存位置？

最佳答案

哈希表或字典是一种存储键值对的数据结构。哈希表的优点是给定一个键找到对应的值是相当快的。简而言之，在哈希表中查找键值对的时间不依赖于表的大小。将其与将键值对存储在列表或数组中进行比较。要查找键值对，您必须从头开始搜索列表，直到找到匹配的键。列表越长，查找键值对所需的时间就越多。使用大 O 表示法，您可以说在哈希表中查找键的顺序为 O(1)，而使用线性搜索在列表中查找键的顺序为 O(N)(简化)。

要在哈希表中插入键值对，您首先必须计算键的哈希码。在 .NET 中，所有对象都有一个名为 GetHashCode 的方法返回该特定对象的哈希码(32 位整数)。相等的对象返回相同的散列码很重要，但如果不同的对象返回不同的散列码也非常有用。请注意不同对象不能返回相同哈希码的误解 - 它们可以，但会导致冲突(见下文)。

例如考虑两个字符串的哈希码:

"Boo" 0x598FD95A
"Foo" 0x598FD8DE

尽管字符串非常相似，但它们具有不同的哈希码。

我在这里稍微简化了一些事情，以关注哈希表的重要方面，所以现在让我们在内部说一下 Dictionary<TKey, TValue>将键值对存储在数组中。要在该数组中找到存储键值对的索引，您必须计算键的散列码对数组大小的模数。假设数组的大小为 5:

Index("Boo") = 0x598FD95A % 5 = 4
Index("Foo") = 0x598FD8DE % 5 = 0

这导致了这个内部哈希表数组:

+---+---------+
| 0 | "Foo"   |
+---+---------+
| 1 | (empty) |
+---+---------+
| 2 | (empty) |
+---+---------+
| 3 | (empty) |
+---+---------+
| 4 | "Boo"   |
+---+---------+

在哈希表中查找条目非常快。您只需以内部数组的大小为模计算 key 的哈希码，并检索该索引处的字符串。

现在考虑键“Zoo”:

Index("Zoo") = 0x598FDC62 % 5 = 0

它与键“Foo”具有相同的索引。这导致了所谓的碰撞。哈希表的正确实现必须处理冲突，并且有 different strategies for doing that .此外，随着内部数组填满，数组中的空元素将越来越少，从而导致冲突次数增加。 加载因子 是内部数组中已用元素与总元素之间的比率。在上面的示例中，负载系数为 2/5 = 0.4。当负载因子超过某个阈值时，大多数哈希表实现都会增加内部数组的大小。

如果您想了解更多关于其中一些概念的信息，您将不得不研究其他答案中链接的一些更全面的资源。

关于c# - 散列过程如何在 Dictionary<TKey, TValue> 中工作，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1407563/

中工c#section的34.net

有关c# - 散列过程如何在 Dictionary<TKey, TValue> 中工作的更多相关文章

  1. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

  2. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  3. 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%

  4. ruby - 将散列转换为嵌套散列 - 2

    这道题是thisquestion的逆题.给定一个散列，每个键都有一个数组，例如{[:a,:b,:c]=>1,[:a,:b,:d]=>2,[:a,:e]=>3,[:f]=>4,}将其转换为嵌套哈希的最佳方法是什么{:a=>{:b=>{:c=>1,:d=>2},:e=>3,},:f=>4,} 最佳答案 这是一个迭代的解决方案，递归的解决方案留给读者作为练习:defconvert(h={})ret={}h.eachdo|k,v|node=retk[0..-2].each{|x|node[x]||={};node=node[x]}node[

  5. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  6. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  7. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  8. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  9. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  10. ruby-on-rails - rspec should have_select ('cars' , :options => ['volvo' , 'saab' ] 不工作 - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion在首页我有:汽车:VolvoSaabMercedesAudistatic_pages_spec.rb中的测试代码:it"shouldhavetherightselect"dovisithome_pathit{shouldhave_select('cars',:options=>['volvo','saab','mercedes','audi'])}end响应是rspec./spec/request

随机推荐