LinkedHashMap по сравнению с HashMap! = LinkedList по сравнению с ArrayList
Я считал, что LinkedHashMap имеет более быструю итеративную скорость, чем HashMap, потому что его элементы вдвойне связаны друг с другом. Кроме того, из-за этого, LinkedHashMap медленнее при вставке или удалении элементов. По-видимому, потому что эти ссылки также должны быть обновлены.
Хотя я вижу аналогию с LinkedList по сравнению с ArrayList в этом, элементы LinkedList также вдвойне связаны, я считал, что это выполняет итерации медленнее, чем ArrayList и имеет более быструю вставку и времена удаления.
Почему это? Возможно, я делаю ошибку где-нибудь?
За Ваше здоровье!
4 ответа
Аналогия не работает. LinkedList и ArrayList являются двумя несвязанными реализациями List. LinkedHashMap, однако, имеет ту же структуру данных, что и HashMap, но с LinkedList, вплетенный в него, чтобы сделать итерацию более быстрой и согласованной.
Причина, по которой итерация LinkedHashMap быстрее, чем итерация HashMap, заключается в том, что итерация HashMap должна переитерировать все сегменты, даже пустые. Тот факт, что LinkedHashMap имеет список, указывающий на данные, означает, что он может пропустить пустые корзины. Список в LinkedHashMap является связанным списком, поскольку время удаления остается постоянным (а не O(n), если это был какой-то список, поддерживаемый arrray).
Чтобы перебрать связанный список, нужно следовать каждой ссылке (ссылке) в каждом элементе. Эти ссылки могут указывать практически на любое место, нет гарантии, что следующий элемент следует за текущим в памяти, что плохо для кеширования. Поскольку каждая ссылка должна быть получена, это происходит медленнее. Массивы непрерывны в памяти, а следующий элемент - это просто ячейка памяти текущего элемента, увеличенная с размером элемента.
Для двусвязного списка вставка в любом месте массива выполняется очень быстро, потому что нужно изменить только ссылки на предыдущий и следующий элемент. С другой стороны, массив работает медленнее, потому что вставка в любой точке приведет к копированию всего массива, чтобы освободить место для нового элемента. Даже добавление элемента приведет к тому, что весь массив будет скопирован, если для массива и вновь добавленного элемента недостаточно постоянной памяти.
Вы особенно заметите различия при вставке при работе с большими наборами данных. Независимо от того, насколько быстрой может быть arraycopy () , двусвязный список всегда быстрее вставляется. Поскольку HashMaps редко повторяются и зависят от вставки и порядка, двусвязный список может повысить его производительность.
Некоторые детали:
Порядок итераторов для LinkedHashMap такой же, как порядок вставки в карту. Поэтому часть LinkedList должна "вставить" только в конец (что O(1) для связного списка, который отслеживает хвост), а часть Map делает только вставку в карту, что O(1). Общая вставка в связный список - O(N), а вставка в ArrayList должна скопировать содержимое массива на 1 слот, прежде чем произойдет вставка.
Время выполнения итерации связанных списков (доступ к каждому элементу) «теоретически» такое же, как и для списка массивов. Для обоих требуется O (n) ( Нотация Big-O ). Однако, поскольку распределение памяти для массивов осуществляется в непрерывном блоке памяти (элементы связанных списков выделяются индивидуально и могут находиться где угодно в памяти), кэширование вступает в силу.
{{1 }}