collection.mutable.OpenHashMap vs collection.mutable.HashMap

Question

对于put和get运营OpenHashMap表现优于HashMap大约5倍:https://gist.github.com/1423303

是否HashMap应优先考虑何时OpenHashMap？

Answer 1

您的代码与OpenHashMap的一个用例完全匹配.你的代码:

println ("scala OpenHashMap: " + time (warmup) {  
  val m = new scala.collection.mutable.OpenHashMap[Int,Int]; 
  var i = 0;
  var start = System.currentTimeMillis();
  while(i<100000) { m.put(i,i);i=i+1;};
})

OpenHashMap(scaladoc)的解释:

基于开放哈希方案的可变哈希映射.精确的方案是未定义的,但它应该做出合理的努力以确保具有连续哈希码的插入不会不必要地受到惩罚.特别是,连续整数键的映射应该在没有显着性能损失的情况下工作.

我的重点.这解释了你的发现.何时使用OpenHashMap而不是HashMap？见维基百科.从那里:

链接列表的链式哈希表很受欢迎,因为它们只需要具有简单算法的基本数据结构,并且可以使用不适合其他方法的简单哈希函数.

表操作的成本是扫描所选桶的条目以获得所需的密钥.如果密钥的分布足够均匀,则查找的平均成本仅取决于每个桶的平均密钥数 - 即负载因子.

即使表条目的数量n远远高于时隙数,链接的哈希表仍然有效.它们的性能随负载因子更优雅地(线性地)降低.例如,具有1000个时隙和10000个存储的密钥(负载因数10)的链状哈希表是五到十次超过10,000时隙表(载荷因子1)更慢; 但仍然比普通顺序列表快1000倍,甚至可能比平衡搜索树快.

对于单独链接,最坏的情况是所有条目都插入到同一个桶中,在这种情况下,哈希表无效,并且成本是搜索桶数据结构的成本.如果后者是线性列表,则查找过程可能必须扫描其所有条目; 因此,最坏情况的成本与表中条目的数量n成正比.

这是一般性的解释.与以往一样,您的表现会因用例而异,如果您关心它,您需要对其进行衡量.