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

все,

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

3 71
javascript performance scala-collections

3 ответа:

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

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

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

HashMap.entrySet()

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

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator(); // returns a HashIterator...
    }
    // ...
}

и HashIterator выглядит так:

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;    // next entry to return
    int expectedModCount;   // For fast-fail
    int index;      // current slot
    Entry<K,V> 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<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;
    }

    // ...
}

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

HashMap.набор ключей() и .получить()

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

64

наиболее распространенный случай, когда использование entrySet предпочтительнее набора ключей, - это когда вы перебираете все пары ключ/значение на карте.

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

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

чем:

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

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

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

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

65

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

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

13