5

我不确定这是否是在这里问的正确问题，但请不要杀了我:)

我和一个朋友就 C# 的字典发生了争执……她告诉我，如果我说字典有 1 个元素。并且键的哈希码是 100000，那么字典的内部数组将是 100000 的大小！

这是真的吗？我试图在谷歌上找到答案，但由于某种原因我没有找到那个问题。

4

7 回答 7

3

根据 MSDN，Dictionary 的默认构造函数“具有默认初始容量” 。

它还指出：

如果您可以估计集合的大小，则使用指定初始容量的构造函数消除了在向 Dictionary 添加元素时执行许多调整大小操作的需要。

一个这样的构造函数只需要一个Int32，它初始化内部存储如下：

Dictionary 可以包含的元素的初始数量。

字典的“默认初始容量”实际上是类的内部实现细节，因此不会在文档或公共 API 中公开。

反汇编mscorlib并ilspy检查默认构造函数表明它的实现如下：

public Dictionary() : this(0, null)
{
}

该链式构造函数实现如下：

public Dictionary(int capacity, IEqualityComparer<TKey> comparer)
{
    if (capacity < 0)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
    }

    if (capacity > 0)
    {
        this.Initialize(capacity);
    }

    this.comparer = (comparer ?? EqualityComparer<TKey>.Default);
}

ieInitialize()根本不被默认构造函数直接或间接调用。

Initialize()是设置内部存储的方法。

所以实际上，如果你调用默认构造函数，内部存储大小甚至不会初始化，直到你第一次添加一个项目。所以它的大小基本上为零。

Initialize()最终在您第一次调用时以零值调用.Add()，这设置了事情。

private void Initialize(int capacity)
{
    int prime = HashHelpers.GetPrime(capacity);
    this.buckets = new int[prime];
    for (int i = 0; i < this.buckets.Length; i++)
    {
        this.buckets[i] = -1;
    }
    this.entries = new Dictionary<TKey, TValue>.Entry[prime];
    this.freeList = -1;
}

GetPrime(0)返回3，因此this.buckets设置为包含三个整数的数组。

分配值的行this.entries看起来有点奇怪，但我看不出 100000 的位置。

简短的回答
我认为你的同事错了。

于 2012-09-28T13:18:24.520 回答
2

哈希码（即GetHashCode）用于将项目放入字典使用的存储桶中。

实际使用的容量取决于字典中元素的数量。

用于什么的（可能不准确）伪代码GetHashCode就是这样。

List<List<KeyValuePair<T,J>>> buckets; // let's assume this get's allocated somewhere (the dictionary allocates this internally)
...
public J GetValueFromDictionary(T key)
{
    int bucketIndex = key.GetHashCode() % buckets.Length;
    return buckets[bucketIndex].Find(x => x.Key == key).Single().Value;
}
于 2012-09-28T13:25:20.250 回答
0

只需使用反射器反编译代码并自行验证即可。

于 2012-09-28T13:17:34.660 回答
0

不它不是。类的来源Dictionary<,>证明了这一点。

于 2012-09-28T13:16:30.653 回答
0

这几乎不是这种情况，因为字典的存储比这复杂得多。此外，可能是键的哈希码的值并没有以任何方式定义字典的大小（我不知道它是如何被捏造的）。

现在，让我们分解字典的存储。

只要一个对象被用作字典中的键，它就不能以任何影响其哈希值的方式发生变化。根据字典的相等比较器，字典中的每个键都必须是唯一的。键不能是空引用（在 Visual Basic 中为 Nothing），但值可以是，如果值类型 TValue 是引用类型。

字典需要一个相等的实现来确定键是否相等。您可以使用接受比较器参数的构造函数来指定 IEqualityComparer 通用接口的实现；如果未指定实现，则使用默认的通用相等比较器EqualityComparer.Default。如果类型 TKey 实现 System.IEquatable 泛型接口，则默认相等比较器使用该实现。

虽然很可能会使用哈希码，因为EqualityComparer.Default它是这样定义的：

Default 属性检查类型 T 是否实现了 System.IEquatable 泛型接口，如果是，则返回使用该实现的 EqualityComparer。否则，它返回一个使用 T 提供的 Object.Equals 和 Object.GetHashCode 覆盖的 EqualityComparer。

决不能保证这将是密钥的生成方式。所以，我希望这对你的论点有所帮助。

最重要的是，哈希码无法确定字典的内部大小，字典是可变的，并且会随着Microsoft 所述的项目的添加而增长：

Dictionary 的容量是 Dictionary 可以容纳的元素的数量。随着元素被添加到字典中，容量会根据需要通过重新分配内部数组来自动增加。

你的朋友在争论之前需要做她的研究。哇！

于 2012-09-28T13:22:52.487 回答
0

作为更新，现在微软提供了 .NET 实现的参考代码，这使得事情比通过反编译更容易。这个问题具体请看

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs

您可以看到默认容量为 3，如前面的答案中所述。

于 2020-06-05T20:00:00.403 回答
-1

不，这不是真的。如果我有

Dictionary<int, object[]> dict = new Dictionary<int, object[]>() 
{
    {10000, new object[] { 1, 2, 3, 4 }}
};

这个字典将包含一个索引为 10000 的对象数组，而不是 9999 个空对象数组插槽，后面跟着我们上面输入的对象。答案是否定的，你朋友错了。

我希望这有帮助。

于 2012-09-28T13:17:50.637 回答