Использование ArrayList или HashMap для лучшей скорости

Question

Мне нужен «Список» или «Карта», ... объекта A. Этот список будет добавлен из другого ArrayList. Объект A считается равным другому, если параметр id равен A.

Моя проблема: я хочу добавить объект, которого нет в моем списке. Я задаюсь вопросом между двумя альтернативами реализации. Использование ArrayList или HashMap

1. ArrayList: 

for (A a: source) {if (! (a in ArrayList)) addToArrayList();} 

2. HashMap <id, A> 

for (A a: source) {hasmap.put (a.id, a)} 

который даст более высокую скорость, чтобы добавить большое количество (более 1000 объектов, или большее количество объектов) есть лучший образец для моей проблемы ???

Answer 1

Во-первых, я собираюсь выйти на конечность и заявить, что это две совершенно разные структуры данных: . A List имеет дело с линейным представлением элементов, а Map имеет дело с значениями пары ключей.

Чувство моего желания заключается в том, что вы пытаетесь выбрать между List и Set.

Если вы хотите ввести только уникальные элементы, или, выражаясь более кратко, если вы заботитесь только об уникальных значений, то Set какой-то ваш лучший выбор - вероятно HashSet, если вы не заботитесь о упорядоченность. It provides O(1) time для основных операций, таких как добавление, удаление, содержит и размер.

^{(Интересно, что HashSet подкреплена HashMap, но и обеспечивает интерфейс, похожий на ArrayList.)}

Answer 2

ArrayList имеет производительность O (n) для каждого поиска, поэтому для n поиска его производительность равна O (n^2).

HashMap имеет производительность O (1) для каждого поиска (в среднем), поэтому для n поиска его производительность будет равна O (n).

Пока HashMap будет медленнее сначала и займет больше памяти, он будет быстрее при больших значениях n.

Причина, по которой ArrayList имеет производительность O (n), заключается в том, что каждый элемент должен быть проверен для каждой вставки, чтобы убедиться, что его еще нет в списке. Мы будем делать n вставок, поэтому для всей операции O (n^2).

Причина, по которой HashMap имеет производительность O (1), заключается в том, что алгоритм хэширования принимает одно и то же время для каждого ключа, а затем поиск для поиска ключа также занимает постоянное время. Могут быть случаи, когда хеш-таблица превышает ее коэффициент загрузки и должна быть перераспределена, и это почему она постоянна на avarage.

Итак, чтобы ответить на ваш вопрос, я советую использовать HashMap.