Почему итерация карты медленнее, чем итерация списка?

Question

Мне задали этот вопрос в интервью, и интервьюер хотел обсудить компромиссы по всем подходам, которые я мог придумать:

Разработка и реализация класса TwoSum. Это должно поддерживать следующее операции: добавить и найти.

add - добавить номер во внутреннюю структуру данных.
find - Найти, если существует какая-либо пара чисел, сумма которых равна значению.

Сначала я придумал приведенное ниже решение, которое очень прямолинейно.

Design1:

public class TwoSumDesign1 {
  private final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  public void add(int number) {
    map.put(number, map.getOrDefault(number, 0) + 1);
  }

  public boolean find(int value) {
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
      int i = entry.getKey();
      int j = value - i;
      if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {
        return true;
      }
    }
    return false;
  }
}

Но затем, проведя некоторое исследование, я обнаружил, что мы можем использовать List для хранения всех чисел, и итерация списка происходит быстрее, чем итерация keySet, но я до сих пор не понимаю, почему?

Ссылка от: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

Итерации по представлениям коллекции требуют времени, пропорционального «емкости» экземпляра HashMap (количество сегментов) плюс его размер (количество отображений ключ-значение). Таким образом, очень важно не устанавливать слишком высокую начальную емкость (или слишком низкий коэффициент загрузки), если важна производительность итерации.

design2:

public class TwoSumDesign2 {
  private final List<Integer> list = new ArrayList<Integer>();
  private final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  // Add the number to an internal data structure.
  public void add(int number) {
    if (map.containsKey(number))
      map.put(number, map.get(number) + 1);
    else {
      map.put(number, 1);
      list.add(number);
    }
  }

  // Find if there exists any pair of numbers whose sum is equal to the value.
  public boolean find(int value) {
    for (int i = 0; i < list.size(); i++) {
      int num1 = list.get(i), num2 = value - num1;
      if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2)))
        return true;
    }
    return false;
  }
}

Может кто-нибудь объяснить, какие есть все компромиссы, о которых нам следует подумать в связи с этой проблемой, и почему второе решение быстрее, чем итерация карты keySet?

Answer 1

Прежде всего, позвольте мне упомянуть, что разница в производительности, о которой мы говорим, вряд ли стоит учитывать. Фраза «Таким образом, очень важно не устанавливать слишком высокую начальную емкость (или слишком низкий коэффициент загрузки), если важна производительность итерации», вводит в заблуждение. Это не очень важно. Я бы лучше сформулировал это так: «Таким образом, вы можете не захотеть устанавливать начальную емкость ...»

Теперь, когда мы получили это, давайте перейдем к фактическому ответу.

Это связано с тем, как организована внутренняя структура данных хеш-карты по сравнению с простой организацией списка.

Стандартная реализация хеш-карты использует список «сегментов», где каждый блок представляет собой связанный список узлов. Ключи и значения хранятся в этих узлах. Список сегментов не является плотно заполненным, что означает, что многие записи null.

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

Поскольку узлов столько же, сколько и ключей, обход узлов имеет такую ​​же сложность по времени, как и обход всего 1014 *, но тогда в случае хэш-карты мы также должны посчитать накладные расходы по ходу списка ведер. И чем больше «начальный размер» хэш-карты или чем меньше коэффициент заполнения, тем больше будет null сегментов, что означает, что в списке сегментов, которые вы будете посещать, будет больше записей, только чтобы узнать, что они null и перейти к следующей записи.

Итак, обход HashMap немного дороже, чем обход ArrayList.

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

Answer 2

Обычная ловушка при итерации Map - это итерация по keySet при использовании get(key) для получения значения, связанного с ключом. Вы избежали этого, перебрав entrySet в дизайне 1.

В практическом плане итерация по HashMap, скорее всего, будет дороже из-за локальности данных. Компиляторы могут вводить ряд оптимизаций при циклическом выполнении массива. Они не будут присутствовать, когда у вас есть список Node объектов, поддерживающих HashMap, см. Бьярн Страуструп: почему вы должны избегать связанных списков .

Однако дизайн 1 легче читать и понимать. Это очень важно, преждевременная оптимизация - корень всего зла. Реальная разница в производительности должна быть измерена до того, как вы решите оптимизировать код. Вполне возможно, что новый List, представленный в дизайне 2, фактически снизит производительность из-за большей косвенности в доступе к памяти (две структуры данных против одной).

Answer 3

В случае второго дизайна вводятся две структуры данных (HashMap и List).Насколько я понимаю, когда мы говорим о производительности кода, а затем проверяем оба сценария Эффективная структура данных и использование памяти.

во втором случае нам нужна дополнительная память.

Дизайн первого легче читаетсяи понять, и вполне может быть, что новый Список, представленный в дизайне 2, фактически снизит производительность из-за большего косвенного доступа к памяти.