Производительность HashMap и LinkedHashMap в итерации по значениям()

Ответ 1

Я думаю, что LinkedHashMap должен быть быстрее в обход из-за превосходной реализации nextEntry в своем Iterator

Вот почему:

Пошаговый шаг по пути от реализации values.
Реализация HashMap values такова:

   public Collection<V> values() {
        Collection<V> vs = values;
        return (vs != null ? vs : (values = new Values()));
    }

LinkedHashMap продолжается от HashMap и наследует ту же реализацию.

Разница заключается в реализации Iterator для values в обоих.

для HashMap он простирается от java.util.HashMap.HashIterator

  private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }

но для LinkedHashMap он продолжается от java.util.LinkedHashMap.LinkedHashIterator

 private class ValueIterator extends LinkedHashIterator<V> {
        public V next() { return nextEntry().value; }
    }

поэтому разница существенно сводится к реализации nextEntry.

Для LinkedHashMap он просто вызывает e.after, где e - Entry, но для HashMap есть некоторая работа, связанная с перемещением массива Entry[], чтобы найти следующий следующий.

UPDATE: Код для nextEntry() в HashMap

final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> 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;
        }

Вступление [] не является непрерывным хранилищем. (Между ними могут быть нулевые значения). Если вы посмотрите на приведенный выше код, то что он делает, это точка рядом с текущим и найти следующий следующий, итерации по записи [].

Но Я думаю, что это увеличение производительности будет зависеть от стоимости вставки. Ознакомьтесь с методом addEntry в обоих классах как упражнение.

Ответ 2

Я написал небольшую программу профилирования, создав 1 миллион ключей (Integer) против Boolean.TRUE, повторяя 100 раз. Найдено следующее:

HashMap:-
Create:  3.7sec
Iterate: 1.1sec
Access:  1.5sec
Total:   6.2sec

LinkedHashMap:-
Create:  4.7sec   (30% slower)
Iterate: 0.5sec   (50% faster)
Access:  0.8sec   (50% faster)
Total :  6.0sec

Сбор мусора НЕ сделано, поэтому несколько загрязняет цифры, однако я думаю, что LinkedHashMap имеет преимущество над HashMap, и я буду использовать его в будущем коде.

Ответ 3

Это почти не имеет значения. Вопрос в том, что вам нужно. Если порядок элементов релевантен, вы должны использовать LinkedHashMap. В противном случае вам это просто не нужно, поэтому используйте HashMap.

Ответ 4

Лучшим советом будет "Не бойтесь попробовать", но я уверен, что они очень похожи. Getter для набора значений - O (1), и каждый шаг итератора. Итерация через связанный список столь же тривиальна, как итерация через хэш-ведра с возможным небольшим ребром в favpr связанного списка.

Ответ 5

Я попробовал в UnitTest, итерированные значения() 10000 раз, миллисекунды: 806 против 902. Это почти то же самое.

Ответ 6

Да, будет такая же разность производительности, как и во всех итерациях по сравнению с HashMap по сравнению с LinkedHashMap: HashMap будет занимать время, пропорциональное количеству записей плюс размер хеш-таблицы, и LinkedHashMap просто займет время, пропорциональное количеству записей.