Какова самая быстрая коллекция Java с основными функциями очереди?

Question

Какая самая быстрая коллекция в Java?

Мне нужны только операции для добавления и удаления, порядок не важен, равнозначные элементы не проблема, ничего, кроме добавления и удаления, не имеет значения.

Без ограничений также важен размер.

Эта коллекция будет содержать объекты внутри него.

В настоящее время я использую ArrayDeque, потому что я вижу, что это более быстрая реализация очереди.

Answer 1

ArrayDeque лучше. См. этот тест , полученный из этого блога о результатах сравнительного анализа этого. ArrayDeque не имеет накладных расходов на распределение узлов, которые есть у LinkedList, ни накладных расходов на смещение содержимого массива, оставшегося при удалении, которое имеет ArrayList. В тесте производительности он составляет около 3x , а также LinkedList для больших очередей и даже немного лучше, чем ArrayList для пустых очередей. Для лучшей производительности вы, вероятно, захотите придать ему начальную емкость, достаточно большую, чтобы вместить количество элементов, которое он может удерживать за раз, чтобы избежать большого размера.

Между ArrayList и LinkedList, кажется, что это зависит от среднего количества общих элементов, которое очередь будет содержать в любой момент времени, и что LinkedList превосходит ArrayList, начиная примерно с 10 элементов.

Answer 2

Вы можете использовать java.util.LinkedList - это двусвязное и изогнутое, поэтому добавление к одному концу и взятие от другого - O (1)

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

Обновление: ответ Колина показывает эталонный тестэто делает вывод, что ArrayDeque лучше.Оба имеют O (1) операций, но LinkedList создает новые объекты (узлы), которые немного производительны.Поскольку оба имеют O (1), я не думаю, что было бы слишком неправильно выбирать LinkedList.