collection.mutable.OpenHashMap vs collection.mutable.HashMap

Question

对于put和get操作，OpenHashMap的性能大约是HashMap的5倍：https://gist.github.com/1423303

是否存在应优先于OpenHashMap而不是HashMap的情况

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？参见Wikipedia。从那里开始：

带有链表的

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

表操作的成本是扫描所选存储桶的条目以查找所需键的成本。如果关键字的分布足够均匀，则查找的平均成本仅取决于每个存储桶的平均关键字数量-即，取决于负载因子。

即使当表条目的数量N远远高于槽的数量时，链式哈希表仍然有效。随着负载因子的增加，它们的性能会更加优雅地(线性地)下降。例如，具有1000个槽和10,000个存储键的链式哈希表(加载因子10)比10,000个槽的表慢5到10倍(加载因子1)；但仍然比普通顺序列表快1000倍，甚至可能比平衡搜索树更快。

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

这是一个通用的解释。与以往一样，您的性能将根据用例的不同而不同，如果您关心它，您需要对其进行测量。