Есть ли реализация карты на основе массива?

Question

Насколько мне известно, единственной реализацией Map в Java Collections API, которая упорядочивает свои записи в порядке вставки, является LinkedHashMap, которая поддерживает связанный список.

Почему нет ничего похожего на ArrayMap, который использует массив или ArrayList внутри?Разве различия между ArrayList и LinkedList больше не имеют значения на карте?Или я что-то упускаю, что делает эту структуру данных вообще плохой идеей?И если это так, является ли LinkedHashMap моим единственным вариантом для реализации Map в стандартной библиотеке Java, если я хочу порядок вставки?

Answer 1

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

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

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

Answer 2

Интерфейс Map предоставляет объекты Map.Entry для каждой записи на карте.Это заставляет Map реализации на самом деле иметь эти объекты, которые затем легко связать вместе в двусвязный список.

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

Обе эти вещи исправимы, и это было бы возможносделать Map, который поддерживает порядок вставки, подкрепленный массивом, но это будет немного сложнее, и в этом нет никакого преимущества.