LinkedHashMap против HashMap! = LinkedList против ArrayList

Question

Я читал, что LinkedHashMap имеет более высокую скорость итерации, чем HashMap, потому что его элементы дважды связаны друг с другом. Кроме того, из-за этого LinkedHashMap работает медленнее при вставке или удалении элементов. Предположительно, потому что эти ссылки также должны быть обновлены.

Хотя я вижу аналогию с LinkedList против ArrayList, в том, что элементы LinkedList также являются двусвязными, я прочитал, что он итерирует медленнее , чем ArrayList, и имеет более быстрое время вставки и удаления.

Почему это? Возможно, я где-то ошибаюсь?

ура!

Answer 1

Аналогия не работает. LinkedList и ArrayList являются двумя несвязанными реализациями List. Однако LinkedHashMap - это та же структура данных, что и HashMap, но с вплетенным в нее LinkedList, чтобы сделать итерацию более быстрой и последовательной.

Причина, по которой итерация LinkedHashMap выполняется быстрее, чем итерация HashMap, заключается в том, что итерация HashMap должна выполнять итерацию по всем сегментам, даже по пустым. Тот факт, что LinkedHashMap имеет список, указывающий на данные, означает, что он может пропускать пустые сегменты. Список в LinkedHashMap является связанным списком, поскольку время удаления остается постоянным (а не O (n), если это был какой-либо список с поддержкой массива).

Answer 2

Время выполнения итераций связанных списков (доступ к каждому элементу) «теоретически» совпадает со списком массивов. Оба требуют времени выполнения O (n) ( Big-O ). Однако, поскольку выделение памяти для массивов происходит через непрерывный блок памяти (элементы связанных списков размещаются индивидуально и могут находиться в любом месте памяти), кэширование вступает в силу.

Answer 3

Некоторые детали:

Порядок итераторов для LinkedHashMap такой же, как порядок вставки в карту. Таким образом, часть LinkedList должна только «вставлять» в конце (которая является O (1) для связанного списка, который отслеживает хвост), а часть Map только вставляет карту, которая является O (1). Обычная вставка связанного списка - O (N), и вставка ArrayList должна скопировать содержимое массива через 1 слот, прежде чем вставка может произойти.

Answer 4

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

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

Вы особенно заметите различия при вставке при работе с большими наборами данных. Независимо от того, насколько быстрым может быть arraycopy(), двунаправленный список всегда быстрее для вставки. Поскольку HashMaps редко повторяются и зависят от вставки и порядка, двусвязный список может повысить производительность.