c# - .net 中的 HashTable/Dictionary 实现选择了哪种类型的冲突解决方案？

Question

我们知道有 2 种经典的冲突解决策略:分离链接和开放寻址。

我想知道在 .net 中为 HashTable/Dictionary 选择了哪一个。

还是使用了其他策略？

Answer 1

这一切都在 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.

记住只有第一句话是我自己的:-)