在Dictionary键中发生散列冲突时会发生什么？ [英] What happens when hash collision happens in Dictionary key?

问题描述

我一直在使用c ++和java编写整个生活，但在C＃上，我觉得它是一个完全不同的动物。

如果c＃中的Dictionary容器发生哈希冲突，它有什么作用？或者它甚至检测到碰撞？

如果在SDL中的类似容器中发生冲突，有些会使关键值部分将数据链接到关键值部分（如链接列表），或者某些人会尝试查找不同的哈希方法。

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

我正在尝试为每位用户创建一个计数器。并且设置用户＃没有定义，它可以增加或减少。我希望数据的大小超过1000.

所以，我想：

• 快速访问最好不要O（n），由于需求，我有接近O（1）的重要性，所以我需要确保我能够在他们能够执行某些愚蠢的事情之前强制注销人员。


• 动态增长和收缩。


• 唯一数据。



HashMap是我的解决方案，看起来Dictionary是类似于C＃中的HashMap ...
>只要一个对象实现 GetHashCode（），就可以通过 Dictionary> 正确处理散列冲突$ c>和 Equals（）正确，相应的实例将从字典返回。




首先，不应该对 Dictionary<>< / code>在内部如何工作做任何假设 - 这是一个可能随时间而改变的实现细节。话说回来......





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





从性能的角度来看，您可能还希望提供一个 GetHashCode（）的实现，该实现可以生成很好的值分布以减少散列码冲突的频率。散列码冲突的主要缺点是，它将字典从性能方面降低到列表中。只要两个不同的对象实例产生相同的散列码，它们就会存储在字典的同一个内部存储桶中。这样做的结果是必须执行线性扫描，在每个实例上调用 Equals（）直到找到匹配。




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

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

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.

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

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.

So, I want :

• fast Access preferably not O(n), It important that I have close to O(1) due to requirement, I need to make sure I can force log off people before they are able to execute something silly.
• Dynamic growth and shrink.
• unique data.

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

解决方案

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.

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

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.

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.

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