collection.mutable.OpenHashMap против collection.mutable.HashMap - PullRequest
Новая
       1

collection.mutable.OpenHashMap против collection.mutable.HashMap

7 голосов
/ 07 декабря 2011

Для операций put и get OpenHashMap превосходят HashMap примерно в 5 раз: https://gist.github.com/1423303

Есть ли случаи, когда HashMap предпочтительнее, чем OpenHashMap?

1 Ответ

6 голосов
/ 07 декабря 2011

Ваш код точно соответствует одному из вариантов использования 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 слотами и 10 000 хранимых ключей (загрузка коэффициент 10) в пять-десять раз медленнее таблицы на 10 000 слотов (загрузка фактор 1); но все же в 1000 раз быстрее, чем обычный последовательный список, и, возможно, даже быстрее, чем сбалансированное дерево поиска.

Для отдельной цепочки наихудший сценарий - это когда все записи были вставлены в то же ведро, в этом случае хеш-таблица неэффективен, и стоимость поиска данных ведра состав. Если последний является линейным списком, процедура поиска может придется сканировать все его записи; поэтому стоимость в худшем случае пропорциональна на количество n записей в таблице.

Это общее объяснение. Как и в случае с этими вещами, ваша производительность будет варьироваться в зависимости от варианта использования, если вы заботитесь об этом, вам нужно измерить его.

...