HashMap или TreeMap или LinkedHashMap, который быстрее итерации?

Ответ 1

Ни один из других ответов здесь не учитывает влияние кэша процессора, которое может быть огромным при итерации.

Один из способов улучшить это - использовать только один массив чередующихся ключей и значений (клавиши с четными индексами, значения на нечетных). Это будет тесно группировать эти элементы данных и максимально использовать кеш, по крайней мере, для ссылок.

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

Ответ 2

HashMap будет, как правило, самым быстрым, так как он обладает наилучшим поведением кэша (HashMap выполняет итерацию непосредственно над базовым массивом, тогда как TreeMap и LinkedHashMap выполняет итерацию по связанным структурам данных).

Вы можете использовать ImmutableMap или UnmodifiableMap, если карта не изменится после ее инициализации

Ответ 3

Если ваша карта используется только для перебора элементов, и скорость итерации важна, то преобразование карты в ArrayList и повторение ее, это будет самый быстрый способ.

Ответ 4

Я бы не использовал карту. Если все, что вам нужно, - это перебирать записи, создайте новый ArrayList из того, что вам нужно, и используйте это - вы не можете получить быстрее, чем ArrayList для итерации.

// Which map you use only chooses the order of the list.
Map<Key,Value> map = new HashMap<>();
// The list to iterate for maximum speed.
List<Map.Entry<Key,Value>> list = new ArrayList<>(map.entrySet());

Таким образом, вы выполняете итерацию по набору записей только один раз, чтобы создать список. С этого момента вы повторяетесь снова и снова по списку, что, безусловно, должно быть близко к оптимальному.

Примечание Изменено от LinkedList до ArrayList по предложению Марко.

Ответ 5

Я согласен с ответом Zim-Zam и добавляю что-то: если вам нужно получить доступ к ключам и значениям во время итерации, самый быстрый способ - entrySet(), как обсуждалось здесь.

Теперь, если вы уверены, что карта никогда не изменится, почему бы не использовать отдельную структуру данных для итерации? например: повторить по завершенной карте и заполнить ее содержимым пару массивов, один с ключами, а другой со значениями в тех же соответствующих положениях. Тогда перемещение этих массивов будет таким же быстрым, насколько это возможно.

Ответ 6

Map.forEach(BiConsumer) почти всегда быстрее, чем итераторы, иногда с большим отрывом. Если вы суммировали значения, например:

public class TestForStackOverflow {
    int sum = 0;

    // Or whatever Map you are using
    Map<Object, Integer> map = new HashMap();

    static class C implements BiConsumer<Object, Integer> {
        int sum = 0;

        @Override
        public void accept(Object k, Integer v) {
            sum += v;
        }
    }

    public int getSum(Map map) {
        C c = new C();
        map.forEach(c);
        return c.sum;
    }

    public int getSum2(Map map) {
        map.forEach((k, v) -> sum += v);
        return sum;
    }
}