字典/ hash_map密钥大小

计算密钥的哈希值并除以质数。一般来说，这是否有任何标准的素数（比如32/64位）？字典/ hash_map密钥大小

我的理解是哈希表是不可调整大小/可调整和它的内部数组取决于此。如果我只有5个元素的散列表，那么在关键空间中会有浪费吗？

编辑：我应该更好的框架。在C++ hash_map（boost）或C＃Dictionary中使用的一般方法是什么

2010-11-09 tvr

如果你只有5个元素，为什么要使用哈希表呢？ – 2010-11-09 04:17:14

所以你从来没有使用5个元素的字典？问题是为什么不呢？这是一个假设性问题。或者，您建议使用什么边界号码？ – tvr 2010-11-09 04:20:22

我想我已经创建了一个字典，最终只有五个元素。尽管如此，我会以更大的尺寸分配它（可能超过10个）以减少碰撞的可能性。 – 2010-11-09 16:49:37

实际上，哈希表大小可以自动调整。你可能要做的是分配一个大小为N的数组，使用哈希模N（某个素数）来索引数组。如果你跟踪你的分配密度，那么当它增加到一定的阈值以上时，你可以分配一个大小为N1的新数组（一些较大的素数），然后复制旧数组中的每个元素，将哈希函数与新模模寻找它在新的哈希表中的位置。最后，您取消分配旧数组并使用新的更大阵列。

来源

2010-11-09 04:21:16

谢谢！我应该更好地构思这一点。在C++ hash_map（boost）或C＃Dictionary中遵循的一般方法是什么？ – tvr 2010-11-09 04:28:37

通常，素数被用作内部数组的大小。也就是说，如果有人要求一个包含100个项目的哈希表，那么选择大于等于100的下一个素数就是大小。在这种情况下，您的桌面尺寸为101.

但这不是唯一的方法。

来源

2010-11-09 04:19:41

为什么不使用Reflector来查看C＃Dictionary或HashTable的实现？格雷格和吉姆的答案都是正确的一般性术语和C＃实现。

总之，C＃字典实现使用一个质数（大于它的容量）作为内部桶数组的大小，并用它来分割哈希码。每当需要调整内部阵列的大小时，它将使用现有容量的两倍作为新容量。

来源

2010-11-09 06:43:24 VinayC

字典/ hash_map密钥大小

回答

相关问题