我的程序检索要通过字符串ID引用的元素的有限且完整的列表。我正在使用.Net Dictionary<string, MyClass>存储这些元素。我个人不知道会有多少个元素。可能是几个。可能是数千个。
给定程序确切知道将在哈希表中放入多少个元素，它应该指定什么作为表的容量。显然，它至少应包含它将包含的元素数量，但是仅使用该数量可能会导致大量冲突。
是否有指南为已知数量的元素选择哈希表的容量，以平衡哈希冲突和内存浪费？
编辑：我知道哈希表的大小可以更改。我首先要避免的是将其保留为默认分配，然后立即添加数千个元素，从而导致无数的调整大小操作。一旦填充，我就不会添加或删除元素。如果知道发生了什么，可以确保预先有足够的空间。我的问题涉及哈希冲突与内存浪费之间的平衡。
最佳答案
这是一个主观的问题，但是让我尽力回答这个问题（从CLR 2.0的角度来看。仅因为我还没有探索CLR 4.0词典中是否有任何变化）。
您正在使用键入字符串的字典。由于可能存在无限可能的字符串，因此可以合理地假设每个可能的哈希码都是“同等可能”。换句话说，对于字符串类，2 ^ 32哈希码（int的范围）中的每一个都同样可能。 BCL中的Dictionary的当前版本从由此获得的任何32位哈希码中删除第32位，实质上是获得31位哈希码。因此，我们要处理的范围是2 ^ 31个唯一的同样可能的哈希码。
请注意，哈希码的范围不取决于字典包含或可以包含的元素数量。
字典类将使用此哈希码将存储桶分配给“ Myclass”对象。因此，从本质上讲，如果两个不同的字符串返回相同的31位哈希码（假设BCL设计人员非常明智地选择了字符串哈希函数，则此类实例应公平分配），两者都将分配相同的存储桶。在这种哈希冲突中，什么也做不了。
现在，在Dictionary类的当前实现中，可能甚至发生了不同的哈希码（再次为31位）仍然出现在同一存储桶中的情况。桶索引的标识如下：
hash = <31 bit hash code>
pr = <least prime number greater than or equal to current dictionary capacity>
bucket_index = hash modulus pr
因此，每个格式（pr * factor + bucket_index）的哈希码都将在同一存储桶中结束，而不考虑因素部分。
如果要绝对确定所有可能的31位哈希码都以不同的存储桶结尾，唯一的方法是强制pr大于或等于最大可能的31位哈希码。换句话说，请确保每个哈希码都采用（pr * 0 + hash_code）的形式，即pr应该大于2 ^ 31。通过扩展，这意味着字典容量应至少为2 ^ 31。
请注意，最小化哈希冲突所需的容量完全不取决于您要在字典中存储的元素数量，而是取决于可能的哈希码范围。
可以想象2 ^ 31是巨大的巨大内存分配。实际上，如果您尝试将2 ^ 31指定为容量，将有两个长度为2 ^ 31的数组。考虑到在32位计算机上，RAM上的最大可能地址是2 ^ 32 !!!!!
如果由于某种原因，字典的默认行为对您而言是不可接受的，并且对您来说最大程度地减少哈希冲突（或者更确切地说是桶冲突）对于您至关重要，那么您仅希望提供自己的哈希代码（即您可以不使用字符串作为键）。这样的哈希码应牢记要获取桶索引的公式，并努力将可能的哈希码范围最小化。最简单的方法是为唯一的MyClass实例增量分配一个数字/索引，然后将此数字用作您的哈希码。然后，您可以将MyClass实例的总数指定为字典容量。但是，在这种情况下，可以很容易地维护数组而不是字典，因为您知道对象的“索引”和索引是递增的。
最后，我想重申一下其他人所说的话，“不会有无数的调整大小”。字典每次发现自身空间不足时，其容量都会加倍（四舍五入为大于或等于新容量的最接近质数）。为了节省一些处理，您可以很好地将容量设置为您拥有的MyClass实例的数量，因为在任何情况下，字典都需要这么大的容量来存储实例，但这不会使“哈希冲突”最小化，通常情况下，足够快。