高效的Hashmap使用

Question

使用散列图的更有效方法是什么？

A)使用多个较小的哈希图,或

B)将所有对象存储在一个巨型hashmap中？

(假设密钥的哈希算法相当有效,导致很少的冲突)

澄清:选项B意味着按主键隔离 - 即不需要额外的查找来确定使用哪个实际的散列映射.(例如,如果查找键是字母数字,则Hashmap 1存储A,Hashmap 2存储B,等等.)

Answer 1

绝对是B.散列表的优点是每次查找的平均比较次数与大小无关.

如果将地图拆分为N个较小的哈希图,则每次查找时必须平均搜索其中一半.如果较小的哈希图具有与较大的图所具有的相同的加载因子,则将比较的总数增加约N/2倍.

如果较小的哈希图具有较小的加载因子,则会浪费内存.

所有这一切都假设您在较小的哈希映射之间随机分配密钥.如果根据键的某些功能(例如字符串前缀)分发它们,那么您创建的是一个trie,这对于某些应用程序是有效的(例如,在Web表单中自动完成).