LinkedHashMap has underlying double-linked list, which enables preservation of the insertion order during the iteration. Non-structural changes, i.e. replacement of the value of an already inserted key, does not affect iteration order. However, I am still wondering, whether remove(key) operation changes the iteration order in LinkedHashMap. As I have tested on really small examples, it does not affect the order of the elements, except for the missing element, which is not included during iteration, obviously - but anecdotes are not proofs. Supposedly, removal works as if in LinkedList (where the halves of the list split are at the index of the element are joined together) - on the other hand, the programmer maybe should take into account rehashing or reallocation.

I am really confused and after reading the documentation of LinkedHashMap thoroughly, also still very doubtful, as I need a structure which preserves the order of insertion but enables an easy lookup and removal of the entries.

CodePudding user response：

The remove() method of the LinkedHashMap class in Java does not change the iteration order of the map. When you iterate over a LinkedHashMap, the elements will be returned in the order in which they were inserted.

This is because a LinkedHashMap maintains a doubly-linked list internally, which allows it to maintain the insertion order of the elements. When you call the remove() method, the element is removed from the map, but the insertion order of the remaining elements is preserved.

Here is an example of how the remove() method works on a LinkedHashMap:

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);

// Remove the "banana" element from the map
map.remove("banana");

// Iterate over the map and print the elements
for (Map.Entry<String, Integer> entry : map.entrySet()) {
  System.out.println(entry.getKey()   ": "   entry.getValue());
}

In the example above, we create a LinkedHashMap and add three elements to it. We then remove the "banana" element from the map using the remove() method. Finally, we iterate over the map and print the remaining elements.

The output of this code will be

apple: 1
cherry: 3

As you can see, the iteration order of the map is preserved, and the elements are returned in the order in which they were inserted. The "banana" element is removed from the map, but the "apple" and "cherry" elements remain in their original positions.

CodePudding user response：

I am really confused and after reading the documentation of LinkedHashMap thoroughly, also still very doubtful ...

Here's the relevant part of the specification.

"This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.")

^{The "normally" refers to the fact that you can create a LinkedHashMap in which the iteration order is access-order.}

That says nothing about the order of remaining entries being changed by deletion. Indeed, if an implementation (hypothetically) did change the order when deleting an entry, that would plainly contradict the unqualified statements about iteration order. In other words, it would not conform to the specification.

Conversely, if the spec writers did intend that deletion affects the iteration order, they would have said so explicitly. Just like they mentioned that "reinsertion" doesn't affect it.

As a general rule, specifications are not written to spell out precisely what happens in every possible scenario. If property Y is a logical consequence of a specified property X, then a specification does not need to (and typically won't) state property Y explicitly.

It is normal for specification writers to assume that readers will make the correct logical inferences for themselves.