Deletion in LinkedHashMap vs HashMap

Question

Is it correct that deletion in LinkedHashMap takes linear time. Since we need to delete the key from the linked list that maintains the order of insertion and it would take O(n) time. In regular HashMap deletion takes constant time.

Answer 1

According to the Javadocs, it is not:

This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

LinkedHashMap does not override the HashMap#remove(Object key) method. The latter removes the entry corresponding to the key from the table and calls a recordRemoval() method on the deleted entry, which adjusts the links of the previous and next to the removed one. There is no iteration on the list in order to delete node at a certain index.