Does remove() change iteration order in LinkedHashMap?

Question

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.

Answer 1

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 intended that deletion should affect the iteration order, they would have said so explicitly. Just like they did 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.