LinkedHashMap LIFO или FIFO?
Связан ли HashMap LIFO или FIFO по своей природе? Если моя карта имеет форму ->
map.put(1,"one");
map.put(2,"two");
какой порядок был бы, если бы я итерации на карте с помощью набора ключей??
РЕДАКТИРОВАТЬ: Я думаю, что на самом деле я перепутал две разные концепции. Позвольте мне перефразировать вопрос. Каков будет порядок, в котором я сталкиваюсь с количествами, используя набор записей? Спасибо за указание, что, кстати, я не собираюсь удалять любые записи.
4 ответа
В связанной хэш-карте элементы в резервном двусвязном списке добавляются в конце (ясно: для сохранения порядка итераций), но могут быть удалены из любой части списка, так как элементы удаляются с карты, неправильно пометьте список поддержки (и, соответственно, карту) как LIFO или FIFO, это ни то, ни другое - на карте нет понятия порядка удаления, и, следовательно, порядок удаления для списка поддержки в связанной хэш-карте не может быть принят.
Что гарантирует связанная хэш-карта , так это то, что перебор ее содержимого (будь то ключи или записи) будет происходить в том же порядке, в котором элементы были вставлены в карту; из документации:
Эта реализация отличается от HashMap тем, что поддерживает двусвязный список, проходящий через все его записи. Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки).
РЕДАКТИРОВАТЬ:
Что касается последнего редактирования вопроса, LinkedHashMap гарантирует, что порядок итераций keySet() будет в том же порядке, в котором были вставлены элементы: 1, 2 для примера в вопросе. Это не имеет ничего общего с FIFO/LIFO, эти понятия имеют дело с порядком, в котором элементы удаляются из структуры данных, и они не связаны с порядком итераций после вставки элементов.
LinkedHashMap для цитирования из javadocs - это "Хэш-таблица и реализация связанного списка интерфейса Map с предсказуемым порядком итераций" . Таким образом, набор ключей будет возвращать ключи в соответствии с порядком вставки, по существу, FIFO.
Когда порядок доступа не используется (стандартный случай), вы можете рассматривать LHM как связанный список с очень быстрым доступом O(1) по ключу.
В этом аспекте это FIFO, когда порядок доступа не используется (посмотрите на c-tors). Когда используется порядок доступа, порядок вставки не имеет значения, есть ли get() операции, как они переупорядочивают записи. смотреть на protected boolean removeEldestEntry(Map.Entry<K,V> eldest) старший =FIFO.
По сути, LHM - это хороший двусвязный список Map.Entry<Key, Value> с хэш-индексом над ключами. Я сам никогда не использую ванильный HashMap, как в его нынешнем значении. он имеет очень мало преимуществ по сравнению с LHM - меньший объем памяти, но ужасная итерация. Java8 (или 9), возможно, может, наконец, исправить HashMap, надеюсь, Даг Ли будет добиваться своего.
Согласно Java-документам, если бы вы перебирали карту, набор ключей был бы в порядке вставки. Таким образом, первый ключ, который вы получаете, является первым введенным ключом поверх существующих ключей. Обратите внимание, что повторная вставка пары ключ-значение не меняет исходную позицию ключа.