Оптимизация скорости вставки в java.util.Map/Set

Question

Есть ли способ оптимизировать скорость вставки в java.util.Collection, указав порядок элементов?

Например

java.util.Set<String> set = java.util.TreeSet<String>(); 

будет это решение:

set.add("A"); 
set.add("B"); 
set.add("C"); 
set.add("D"); 
set.add("E"); 

быть быстрее, чем эта (случайном порядке)?

set.add("E"); 
set.add("D"); 
set.add("C"); 
set.add("A"); 
set.add("B"); 

(и тот же вопрос для других коллекций: HashMap, hastable ...)

Благодаря

Answer 1

время

вставки для red-black tree (который используется для реализации в Java TreeSet/TreeMap) гарантируются худшим случай должен быть O (log n). Это может быть быстрее, если элементы находятся в определенном порядке, но я не уверен, что бы это было (возможно, предварительно отсортированный был бы самым быстрым?).

Вставка в хэш-таблицу - это операция O (1) (постоянное время). Главное, что сделано для вставки - это расчет hashcode.

Редактировать: Starblue предлагает предварительно отсортированные данные, которые могут привести к наихудшему результату, чтобы вы могли попробовать рандомизированный заказ.

Answer 2

Легкий ответ - «время и посмотреть».

Другой ответ: «Это не имеет значения». Кажется, это микро-оптимизация, которая вряд ли стоит усилий. Я думаю, что он относится к категории "The Sad Tragedy of Micro-Optimization Theater".

Answer 3

Существует, естественно, огромная разница между коллекциями на основе хэша и основанными на деревьях.

Использование на основе дерева полезно для упорядочения элементов для вставки (например, сравнения между строками), поэтому, когда у вас есть сопоставимые объекты (например, строка), их лучше использовать. TreeSet/TreeMap/etc. в стандартной коллекции должно быть сбалансировано (красно-черное дерево), поэтому порядок вставки не имеет большого значения. Если бы он не был сбалансирован, тогда порядок вставки имел бы значение, поскольку вы могли бы получить цепочку вместо дерева.

В хэш-таблицах коэффициент загрузки и функция хеширования решают все, но если вы имеете дело со строками, возможно, вам лучше не беспокоиться о хэшировании.

Если вам понадобится набор строк для многих строк с перекрытиями, Trie может быть более эффективным с точки зрения памяти, но я не думаю, что в библиотеке есть один.

Answer 4

Нет для java.util.Map и java.util.Set, потому что это интерфейсы, и существуют различные реализации.

Для конкретных реализаций это не стоит оптимизировать. Если у вас проблемы с производительностью, вы выбираете более подходящую реализацию или переосмысливаете, что и как вам нужно хранить.

Вставка 5000 случайных чисел в HashSet занимает около миллисекунды на ноутбуке, на котором работает миллион, поэтому сколько миллионов элементов вы хотите вставить, чтобы сделать такую ​​оптимизацию стоящей?

Answer 5

Примите меры предосторожности, чтобы учитывать характеристики вашей структуры данных. Для одного крайнего примера вставка элементов в двоичное дерево в отсортированном порядке приведет к связанному списку.