Использование 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.
