CODEWITHSUNDEEP
javacollectionshashmaptime-complexity
user1745356
user1745356

Reputation: 4673

Deletion in LinkedHashMap vs HashMap

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.

Upvotes: 7

Views: 5396

Answers (2)

juanotto
juanotto

Reputation: 120

LinkedHasMap uses an Entry that subclasses HashMap.Entry, so the cost is higher but still constant.

Every time a entry is deleted in HashMap the method recordRemoval(HashMap m) is called. Its implementation in HashMap.Entry is empty but LinkedHasMap. Entry just delete the entry from the list):

/**
 * Removes this entry from the linked list.
 */
private void remove() {
    before.after = after;
    after.before = before;

}

The sequence is as follows:

  • remove implementation in HashMap calls removeEntryForKey (HashMap:line551)

    public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

  • removeEntryForKey in HashMap calls entry.recordRemoval(this) (HashMap:line560)

    final Entry<K,V> removeEntryForKey(Object key) {
    [...]
    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            [...]
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
    return e;
}

  • recordRemoval implementation in LinkedHasMap.Entry calls remove method above, which is O(1) (LinkedHashMap:line357)

    void recordRemoval(HashMap<K,V> m) {
    remove();
}

Source for HashMap: http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/HashMap.java

Source for LinkedHashMap: http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/LinkedHashMap.java

Upvotes: 4

M A
M A

Reputation: 72854

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.

Upvotes: 10

Related Questions