scala - collection.mutable.OpenHashMap 与 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 ) 的解释:

A mutable hash map based on an open hashing scheme. The precise scheme is undefined, but it should make a reasonable effort to ensure that an insert with consecutive hash codes is not unneccessarily penalised. In particular, mappings of consecutive integer keys should work without significant performance loss.

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

Chained hash tables with linked lists are popular because they require only basic data structures with simple algorithms, and can use simple hash functions that are unsuitable for other methods.

The cost of a table operation is that of scanning the entries of the selected bucket for the desired key. If the distribution of keys is sufficiently uniform, the average cost of a lookup depends only on the average number of keys per bucket—that is, on the load factor.

Chained hash tables remain effective even when the number of table entries n is much higher than the number of slots. Their performance degrades more gracefully (linearly) with the load factor. For example, a chained hash table with 1000 slots and 10,000 stored keys (load factor 10) is five to ten times slower than a 10,000-slot table (load factor 1); but still 1000 times faster than a plain sequential list, and possibly even faster than a balanced search tree.

For separate-chaining, the worst-case scenario is when all entries were inserted into the same bucket, in which case the hash table is ineffective and the cost is that of searching the bucket data structure. If the latter is a linear list, the lookup procedure may have to scan all its entries; so the worst-case cost is proportional to the number n of entries in the table.

这是一个笼统的解释。与以往一样，您的性能将因用例而异，如果您关心它，则需要对其进行测量。