字典是如何在内部维护的？

Question

当我说

Dictionary<int,string>

这是否等同于两个不同的数组，例如：

int[] keys =new int[] { 1, 2, 3 };
string[] values=new string[]{"val1","val2","val3"};

- user193276

Answer 1

这并不太遥远。通过反编译工具Reflector查看源代码，似乎使用了三个内部集合：

private Entry<TKey, TValue>[] entries;
private KeyCollection<TKey, TValue> keys;
private ValueCollection<TKey, TValue> values;

请注意，还有一个int[] buckets变量用于跟踪哈希码冲突时所需的桶。

这些变量的目的应该都很容易理解。这并不特别令人惊讶，因为Dictionary类已知并记录为提供（理想情况下，每个桶一个项）O(1)查找时间。

- Noldorin

Answer 2

在MSDN上已经清楚地说明了这一点：

Dictionary(Of TKey, TValue)泛型类提供了从一组键到一组值的映射。每次向字典中添加内容时，都需要提供一个值和与之相关联的键。通过使用其键检索值非常快速，接近O(1)，因为Dictionary(Of TKey, TValue)类是作为哈希表实现的。

- Bolek Tekielski

---

当然，这一切都是真实的，但并没有完全回答问题。当然，在现实中，内部实现并不重要，而是关于计算复杂度的问题。 - Noldorin

Answer 3

这是一个哈希表。对于每个键，字典都会计算其哈希码，并使用它作为指针来存储值的位置。如果有两个键匹配相同的哈希码，则称为冲突，在这种特殊情况下，字典内部使用二叉树来处理。

字典（哈希表）的算法复杂度为O（1），在最坏的情况下为O（log（N））（最坏的情况是我们只处理冲突），其中N是字典中元素的数量。

- Vitaliy Liptchinsky

Answer 4

不，它是一个哈希表。嗯，它不完全是一个哈希表，但它非常密切相关。

http://en.wikipedia.org/wiki/Hash_table。

http://www.kirupa.com/net/dictionary_hashtable.htm

- kemiller2002