我的程序检索我想通过字符串 ID 引用的元素的有限且完整的列表。我正在使用 .NetDictionary<string, MyClass>来存储这些元素。我个人不知道会有多少元素。可能是几个。可能是数千。
鉴于程序确切知道它将在哈希表中放入多少元素，它应该指定什么作为表的容量。显然，它至少应该是它将包含的元素数量，但仅使用该数量可能会导致大量冲突。
是否有为已知数量的元素选择哈希表容量以平衡哈希冲突和内存浪费的指南？
编辑：我知道哈希表的大小可以改变。我首先要避免的是将其保留为默认分配，然后立即添加数千个元素，从而导致无数的调整大小操作。填充后，我不会添加或删除元素。如果我知道发生了什么，我可以确保前面有足够的空间。我的问题与哈希冲突与内存浪费的平衡有关。
您的问题似乎暗示了一个错误的假设，即字典的容量是固定的。它不是。
如果您知道在任何给定情况下字典将至少包含一定数量的元素，那么您可以将该数字指定为字典的初始容量。字典的容量总是至少与其项目数一样大（至少对于 .NET 2 到 4 来说是这样；我相信这是一个未记录的实现细节，可能会发生变化）。
指定初始容量通过消除字典从其默认初始容量增长到您选择的容量时可能发生的分配来减少内存分配的数量。
如果使用的散列函数选择得当，那么冲突的数量应该相对较少，并且对性能的影响应该最小。在某些人为的情况下，指定一个过大的容量可能会有所帮助，但我绝对不会考虑这一点，除非分析表明字典的查找对性能有重大影响。
（作为人为情况的示例，考虑一个int容量为 10007 的字典，其所有键都是 10007 的倍数。在当前实现中，所有项目都将存储在单个存储桶中，因为存储桶通过将哈希码除以容量并取余数来选择。在这种情况下，字典将用作链表，强制它使用不同的容量可以解决这个问题。）
这是一个主观的问题，但让我尽力回答这个问题（从 CLR 2.0 的角度来看。只是因为我还没有探索 CLR 4.0 的字典是否有任何变化）。
您正在使用以字符串为键的字典。由于可能存在无限个可能的字符串，因此可以合理地假设每个可能的哈希码“均等”。或者换句话说，每个 2^32 哈希码（int 范围）都同样可能用于字符串类。BCL 中的当前版本的字典从由此获得的任何 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 实例的数量，因为在任何情况下字典都需要这么多容量来存储实例，但这不会最小化“哈希冲突”，并且在正常情况下将是足够快。
像 HashTable 这样的数据结构用于动态内存分配。但是，您可以在某些结构中提及初始大小。但是，当您添加新元素时，它们的大小会扩大。您无法隐式限制大小。
有许多可用的数据结构，各有优缺点。你需要选择最好的。限制大小不会影响性能。您需要注意添加、删除和搜索，这会影响性能。