Коллекция Java с максимальной производительностью для таблицы поиска с несколькими значениями на ключ?

Question

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

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

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

Какой вариант является наиболее эффективным , или есть другой вариант?

• Multimap

• Map<String, ArrayList<Class>>

• ArrayList<Class> и поиск по предикату?

Answer 1

Ваш выбор должен быть основан на наиболее частой операции, в данном случае поиск.

Lists дает вам наилучшую сложность для вставки O (1) и O (n) для поиска

A MultiMap<A, B> связывает ключ типа A со значением типа Collection

A Map<A, B> связывает ключ типа A со значением типа B.

Итак, a MultiMap<Integer, Set<String>> можно рассматривать как

Map<Integer, Collection<Set<String>>.

Оба дают O (1) вставку, а в худшем случае O (k) k - самый длинный набор значений. k сильно зависит от качества функции ha sh, с хорошей функцией ha sh время поиска может быть O (1).

Я бы использовал go с Map или MultiMap. Если вы инициализируете структуру один раз, а затем никогда не вставляете новые элементы, тогда определенно go с Map.