Соображения производительности для keySet () и entrySet () карты

Все,

Может кто-нибудь, пожалуйста, дайте мне знать, какие проблемы производительности между двумя? Сайт: CodeRanch предоставляет краткий обзор внутренних вызовов, которые понадобятся при использовании keySet () и get (). Но было бы здорово, если бы кто-нибудь мог предоставить точную информацию о streamе, когда используются методы keySet () и get (). Это поможет мне лучше понять проблемы производительности.

Прежде всего, это зависит полностью от того, какой тип Карты вы используете. Но поскольку stream JavaRanch говорит о HashMap, я буду считать, что это реализация, о которой вы говорите. И давайте предположим также, что вы говорите о стандартной реализации API от Sun / Oracle.

Во-вторых, если вас беспокоит производительность при повторении через вашу hash-карту, я предлагаю вам взглянуть на LinkedHashMap . Из документов:

Итерация по представлениям коллекции LinkedHashMap требует времени, пропорционального размеру карты, независимо от ее емкости. Итерация над HashMap, вероятно, будет более дорогой, требуя времени, пропорционального ее пропускной способности.

HashMap.entrySet ()

Исходный код для этой реализации доступен. Реализация в основном просто возвращает новый HashMap.EntrySet . Класс, который выглядит следующим образом:

 private final class EntrySet extends AbstractSet> { public Iterator> iterator() { return newEntryIterator(); // returns a HashIterator... } // ... } 

и HashIterator выглядит

 private abstract class HashIterator implements Iterator { Entry next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } final Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } // ... } 

Итак, у вас есть это ... Это код, который диктует, что произойдет, когда вы перейдете через entrySet. Он просматривает весь массив, который до тех пор, пока емкость карт.

HashMap.keySet () и .get ()

Здесь вам сначала нужно получить набор ключей. Это занимает время, пропорциональное емкости карты (в отличие от размера для LinkedHashMap). После этого вы вызываете get() один раз для каждого ключа. Конечно, в среднем случае с хорошей реализацией hashCode это занимает постоянное время. Тем не менее, это неизбежно потребует много .hashCode и .equals , что, очевидно, займет больше времени, чем просто entry.value() .

Наиболее распространенным случаем, когда использование entrySet является предпочтительным по сравнению с keySet, является то, что вы выполняете итерацию через все пары ключ / значение на карте.

Это более эффективно:

 for (Map.Entry entry : map.entrySet()) { Object key = entry.getKey(); Object value = entry.getValue(); } 

чем:

 for (Object key : map.keySet()) { Object value = map.get(key); } 

Поскольку во втором случае для каждого ключа в keySet map.get() метод map.get() , который – в случае с HashMap – требует, чтобы методы hashCode() и equals() ключевого объекта оценивались в порядке найти соответствующее значение *. В первом случае исключена дополнительная работа.

Edit: Это еще хуже, если вы рассматриваете TreeMap, где вызов get – это O (log2 (n)), то есть для сравнения для воли может потребоваться запустить log2 (n) раз (n = размер карты), прежде чем найти связанное значение.

* В некоторых реализациях карты есть внутренние оптимизации, которые проверяют идентификацию объектов до hashCode() и equals() .

Ниже приведена ссылка на статью, сравнивающую производительность entrySet() , keySet() и values() и советы относительно использования каждого подхода.

По-видимому, использование keySet() выполняется быстрее (кроме того, что это более удобно), чем entrySet() если вам не нужны значения Map.get() .

  • Производительность сериализации C ++
  • Оптимизация производительности сборки x86-64 - Выравнивание и outlookирование ветвлений
  • Как профилировать использование памяти и производительность с помощью инструментов?
  • Сравнение двух байтовых массивов в .NET.
  • Улучшение отражения производительности, какие альтернативы мне следует учитывать
  • Обработка больших растровых изображений
  • Производительность массивов против списков
  • Как найти пару с k-й наибольшей суммой?
  • Виртуальные функции и производительность - C ++
  • Эффективное умножение векторных матриц 4x4 на SSE: горизонтальное добавление и точечный продукт - в чем смысл?
  • Модульная арифметика и оптимизация NTT (конечного поля DFT)
  • Давайте будем гением компьютера.