当前位置：文江博客话题详情

C# .NET hashtable collision

.net 中的 HashTable/Dictionary 实现选择什么类型的冲突解决方案？

发布于 2024-12-04 16:35:59 字数 86 浏览 4 评论 0原文

众所周知，冲突解决有两种经典策略：单独链接和开放寻址。

我想知道.net 中的哈希表/字典选择了哪一个。

还是使用了其他策略？

收藏 0

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

评论（2）

窗影残 2024-12-11 16:35:59

MSDN 上的这篇论文对此进行了全部描述：数据结构的广泛检查使用C#2.0

...称为 rehasing 的碰撞解决技术，即
.NET Framework 的 Hashtable 类使用的技术。在决赛中
部分，我们将看一下 Dictionary 类，它使用碰撞
解析技术称为链接。
....
... Rehasing 的工作原理如下：有一组不同的哈希值
函数，H1 ... Hn，以及在其中插入或检索项目时
哈希表，最初使用H1哈希函数。如果这导致
如果发生碰撞，则尝试 H2，如果需要，则继续尝试 Hn。
上一节只展示了一个哈希函数，即
初始哈希函数（H1）。其他哈希函数非常相似
对于该函数，仅通过乘法因子进行微分。在
一般情况下，哈希函数Hk定义为：

 Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %  (hashsize – 1)))] % hashsize

Dictionary 类与 Hashtable 类在很多方面都有所不同
比一。除了强类型之外，字典还
采用与哈希表不同的冲突解决策略
类，使用称为链接的技术。回想一下，与
探测，如果发生冲突，列表中的另一个槽
桶已尝试过。（通过重新哈希，哈希被重新计算，并且
尝试新的插槽。）但是，通过链接，可以使用辅助数据结构
用于阻止任何碰撞。具体来说，每个插槽
Dictionary 有一个映射到该存储桶的元素数组。在
发生碰撞时，碰撞元素会被添加到
存储桶列表。

请记住，仅第一句话是我自己的:-)

It's all described in this paper on the MSDN : An Extensive Examination of Data Structures Using C# 2.0

...collision resolution technique called rehasing, which is the
technique used by the .NET Framework's Hashtable class. In the final
section, we'll look at the Dictionary class, which uses a collision
resolution technique knows as chaining.
....
... Rehasing works as follows: there is a set of hash different
functions, H1 ... Hn, and when inserting or retrieving an item from
the hash table, initially the H1 hash function is used. If this leads
to a collision, H2 is tried instead, and onwards up to Hn if needed.
The previous section showed only one hash function, which is the
initial hash function (H1). The other hash functions are very similar
to this function, only differentiating by a multiplicative factor. In
general, the hash function Hk is defined as:

 Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %  (hashsize – 1)))] % hashsize

The Dictionary class differs from the Hashtable class in more ways
than one. In addition to being strongly-typed, the Dictionary also
employs a different collision resolution strategy than the Hashtable
class, using a technique referred to as chaining. Recall that with
probing, in the event of a collision another slot in the list of
buckets is tried. (With rehashing, the hash is recomputed, and that
new slot is tried.) With chaining, however, a secondary data structure
is utilized to hold any collisions. Specifically, each slot in the
Dictionary has an array of elements that map to that bucket. In the
event of a collision, the colliding element is prepended to the
bucket's list.

Remember only the first sentence is my own :-)

回复收藏 0 原文

眼泪淡了忧伤 2024-12-11 16:35:59

这实际上是一个非常有趣的问题；我刚刚发表了一篇博客文章< /a> 了解 Dictionary 是如何在幕后实现的。我可能会在稍后的文章中介绍Hashtable。

回复收藏 0 原文

~没有更多了~

关于作者

暂无简介

文章

评论

27 人气

关注发私信

相关话题

热门标签

操作系统程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端

推荐作者

qq_VRzBBA45

文章 0 评论 0

痴情

文章 0 评论 0

。

文章 0 评论 0

Mu.

文章 0 评论 0

凉薄对峙

文章 0 评论 0

不落城

文章 0 评论 0

友情链接

我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的隐私政策了解更多相关信息。单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。

原文