使用哈希图的更有效方法是什么？
A）使用多个较小的哈希图，或
B）将所有对象存储在一个巨大的哈希图中？
（假设密钥的散列算法相当有效，导致冲突很少）
澄清：选项 B 意味着按主键进行隔离——即不需要额外的查找来确定要使用哪个实际的 hashmap。（例如，如果查找键是字母数字，则 Hashmap 1 存储 A，Hashmap 2 存储 B，依此类推。）
问问题
1545 次
3 回答
5
绝对是 B。哈希表的优点是每次查找的平均比较次数与大小无关。
如果您将地图拆分为 N 个较小的散列图，则每次查找都必须平均搜索其中的一半。如果较小的 hashmap 与较大的 map 具有相同的负载因子，则您将比较总数增加大约 N/2 的因子。
如果较小的哈希图具有较小的负载因子，那么您就是在浪费内存。
所有这一切都假设您在较小的哈希映射之间随机分配密钥。如果您根据键的某些功能（例如字符串前缀）分发它们，那么您创建的是trie，这对于某些应用程序很有效（例如，网络表单中的自动完成）。
于 2009-08-01T14:55:32.503 回答
4
这些地图是否在逻辑上不同的地方使用？例如，我不会有一张包含用户、缓存查询结果、记录器等的地图，只是因为您碰巧知道键不会发生冲突。但是，我同样不会将单个地图拆分为多个地图。
为每个从键到值的逻辑映射保留一个 hashmap 。
于 2009-08-01T15:07:23.357 回答
1
除了@Jon 的回答，您可能有实际原因要维护单独的哈希表。
如果您有不同映射的单独表，则可以独立“清除”每个映射；例如，通过调用“清除”或摆脱对相应表的引用。
如果单独的表保存到缓存条目的映射，您可以使用不同的策略来“老化”各个条目。
如果应用程序是多线程的，使用单独的表可以减少锁争用，并且可以（对于某些处理器架构）增加处理器内存缓存命中率。
于 2009-08-01T15:55:03.040 回答