Сложность двух сумм III на LeetCode

Question

Я пытаюсь работать над Two Sum III на LeetCode. Возникает вопрос:

Создайте и реализуйте класс TwoSum. Он должен поддерживать следующие операции : добавьте и найдите. add - Добавить номер во внутренние данные Структура. find - найдите, существует ли какая-либо пара чисел, сумма которых равна значению. Например, добавьте (1); Добавить (3); добавить (5);
находки (4) -> истинная находка (7) -> ложного

Я знаю два приемлемых решений, первый использует список, а второй использует карту. Вот два решения у меня есть:

Реализация списка:

public class TwoSum { 
    private List<Integer> list; 
    public TwoSum() { 
     list = new ArrayList<Integer>(); 
    } 
    public void add(int num) { 
     list.add(num); 
    } 
    public boolean find (int sum) { 
     if(list.size() == 1) 
      return list.get(0) == sum; 
     for (int i = 0; i < list.size(); i++) { 
      if (list.contains(sum - list.get(i))) { 
       if (list.indexOf(sum - list.get(i)) == i) 
        continue; 
       return true; 
      } 
     } 
     return false; 
    } 
} 

Реализация Карта:

public class TwoSum2 { 
    private Map<Integer, Integer> map; 
    public TwoSum2() { 
     map = new HashMap<Integer, Integer>(); 
    } 
    public void add(int num) { 
     if (!map.containsKey(num)) 
      map.put(num, 1); 
     else 
      map.put(num, map.get(num) + 1); 
    } 
    public boolean find(int sum) { 
     if(map.size() == 1) 
      return map.containsKey(sum); 
     for (int num : map.keySet()) { 
      if (map.containsKey(sum - num)) { 
       if (num == sum - num && map.get(num) == 1) 
         continue; 
       return true; 
      } 
     } 
     return false; 
    } 
} 

Два решения должны дать мне такую ​​же сложность, O (1) для дополнения и O (n) для поиска. Однако реализация List выполняется несколько быстрее для нескольких тестовых случаев, которые у меня есть. Единственная причина, по которой я могу думать, это займет некоторое время, чтобы получить хеш-код на карте и найти ключ. Но я не уверен в этом ответе. Каковы возможные причины, по которым реализация карты медленнее?

Спасибо.

Answer 1

Для HashMap существует переменная, называемая коэффициентом загрузки. Если коэффициент загрузки достигнут, HashMap перераспределит больше памяти и перефразирует всю пару значений ключа. В этом случае сложность O (n) для одного действия put, поэтому она может быть медленнее. Проверьте это documentation

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

Как правило, коэффициент загрузки по умолчанию (.75) предлагает хороший обмен между затратами времени и пространства. Более высокие значения уменьшают накладные расходы , но увеличивают стоимость поиска (отраженные в большинстве операций класса HashMap, включая получение и пометку). Ожидаемое количество записей на карте и коэффициент ее загрузки должны быть учтены в учетной записи при настройке начальной емкости, чтобы свести к минимуму число операций повторной обработки. Если начальная емкость больше , максимальное количество записей, деленное на коэффициент нагрузки, не будет переработано .