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

Мне нужен "Список" или "Карта",... объекта 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 объектов или большего количества объектов) Есть ли лучший образец для моей проблемы?

Ответ 1

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

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

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

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

Ответ 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.