Какой из них быстрее? List.contains() или Map.containsKey()

Я пишу алгоритм, в котором я ищу пары значений, которые при объединении дают другое значение, которое я ищу.

Я понял, что использование Map ускорит мой алгоритм от O (n²). Позже я понял, что я действительно не использую значения, содержащиеся в моем Map, поэтому достаточно List.

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

Можете ли вы указать, где я должен искать такую ​​информацию?

Ответы

Ответ 1

list.contains - O (n), тогда как map.containsKey - O (1) для хэшмапов O (logn) для treemaps. Для hashmaps, google для хэш-таблицы. Для treemaps, google для двоичного дерева или аналогичного. В Википедии есть хорошие записи по этим темам.

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

Будьте осторожны, однако, чтобы избежать класса Hashtable. Это археологический артефакт в современной библиотеке. Для вашего случая HashSet, вероятно, лучший выбор.

Ответ 2

Map и List являются интерфейсами, поэтому информация об их реализации и их производительности отсутствует. Но если вы используете самые последние версии (LinkedList или ArrayList для List, а HashMap для Map), метод contains() должен, в худшем случае, пройти весь список и сравните свой элемент с каждой записью. Это операция O (n).

Если вы используете HashMap, реализация радикально отличается: HashMap содержит массив с большим количеством записей, чем элементы в нем (на практике у вас есть размер массива между 4n/3 и 3n/2 для n элементов на карте). Он вычисляет хэш ключа, который является int, и переносит его между 0 и вашим размером массива (пусть это число i). Затем он поместит элемент в индекс i массива (или i+1, i+2... если предыдущие индексы уже приняты). Итак, когда вы проверяете наличие ключа с помощью containsKey, он будет повторно вычислять значение хэша и i и проверять индексы i, i+1..., пока не найдет пустую ячейку массива. Теоретически, вы можете иметь наихудший случай O (n), если массив почти заполнен, все ключи имеют почти идентичные значения i, но с хорошей хэш-функцией у вас есть постоянное время contains и get. (Тем не менее, добавление элементов происходит быстро, если вам не нужно изменять размер массива, который является ДЕЙСТВИТЕЛЬНО медленным - я думаю, вам нужно пересчитать индексы каждой клавиши).

Таким образом, карта действительно быстрее, если вам нужно проверить внешний вид ключа в коллекции и не нужно сохранять порядок (для этого есть SortedHashMap, но я не знаю его производительности), но это займет больше памяти.

Кроме того, если вам не нужна клавиша-значение, вы можете использовать HashSet (которая внутренне такая же, как и HashMap).

Ответ 3

Map.containsKey(), учитывая, что вы используете HashMap, поскольку поиск в HashMap выполняется в O (1).

List.contains() обычно должен прибегать к последовательному поиску или двоичному поиску, поэтому сложность будет по крайней мере O (log n)