当字典键发生哈希冲突时会发生什么? [英] What happens when hash collision happens in Dictionary key?

问题描述

我一生都在用 C++ 和 Java 编写代码，但在 C# 上，我觉得它是一种完全不同的动物.

I've been coding in c++ and java entirety of my life but on C#, I feel like it's a totally different animal.

如果c#中的Dictionary容器发生hash冲突，怎么办?或者它甚至检测到碰撞?

In case of hash collision in Dictionary container in c#, what does it do? or does it even detect the collision?

如果在 SDL 中的类似容器中发生冲突，有些人会像链表一样使键值部分链接数据到键值部分，或者一些人会尝试找到不同的哈希方法.

In case of collisions in similar containers in SDL, some would make a key value section link data to key value section like linked list, or some would attempt to find different hash method.

[上午 10:56 更新6/4/2010]

[Update 10:56 A.M. 6/4/2010]

我正在尝试为每个用户创建一个计数器.而set user#没有定义，它既可以增加也可以减少.而且我预计数据的大小将超过 1000.

I am trying to make a counter per user. And set user # is not defined, it can both increase or decrease. And I'm expecting the size of data to be over 1000.

所以，我想要:

• 快速访问最好不是 O(n)，重要的是我有接近 O(1) 的要求，我需要确保在他们能够执行一些愚蠢的事情之前我可以强制注销他们.
• 动态增长和收缩.
• 独特的数据.

Hashmap 是我的解决方案，看起来Dictionary 类似于c# 中的hashmap...

Hashmap was my solution, and it seems Dictionary is what is similar to hashmap in c#...

推荐答案

哈希冲突由 Dictionary<> 正确处理 - 只要对象实现GetHashCode() 和 Equals() 正确，将从字典中返回适当的实例.

Hash collisions are correctly handled by Dictionary<> - in that so long as an object implements GetHashCode() and Equals() correctly, the appropriate instance will be returned from the dictionary.

首先，您不应该对 Dictionary<> 的内部工作方式做出任何假设 - 这是一个可能会随着时间而改变的实现细节.话虽如此....

First, you shouldn't make any assumptions about how Dictionary<> works internally - that's an implementation detail that is likely to change over time. Having said that....

您应该关心的是您用于键的类型是否正确实现了 GetHashCode() 和 Equals().基本规则是 GetHashCode() 必须在对象的生命周期内返回相同的值，并且 Equals() 在两个实例表示同一个对象时必须返回 true.除非你覆盖它，Equals() 使用引用相等——这意味着它只有在两个对象实际上是同一个实例时才返回 true.您可以覆盖 Equals() 的工作方式，但是您必须确保相等"的两个对象也产生相同的哈希码.

What you should be concerned with is whether the types you are using for keys implement GetHashCode() and Equals() correctly. The basic rules are that GetHashCode() must return the same value for the lifetime of the object, and that Equals() must return true when two instances represent the same object. Unless you override it, Equals() uses reference equality - which means it only returns true if two objects are actually the same instance. You may override how Equals() works, but then you must ensure that two objects that are 'equal' also produce the same hash code.

从性能的角度来看，您可能还想提供一种 GetHashCode() 的实现，以生成良好的值传播以减少哈希码冲突的频率.哈希码冲突的主要缺点是，它在性能方面将字典简化为列表.每当两个不同的对象实例产生相同的哈希码时，它们就会存储在字典的同一个内部存储桶中.这样做的结果是，必须执行线性扫描，在每个实例上调用 Equals() 直到找到匹配项.

From a performance standpoint, you may also want to provide an implementation of GetHashCode() that generates a good spread of values to reduce the frequency of hashcode collision. The primarily downside of hashcode collisions, is that it reduces the dictionary into a list in terms of performance. Whenever two different object instances yield the same hash code, they are stored in the same internal bucket of the dictionary. The result of this, is that a linear scan must be performed, calling Equals() on each instance until a match is found.

这篇关于当字典键发生哈希冲突时会发生什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！