Использование двойного связного списка в LinkedHashMap над Single LinkedList

Question

Я знаю, что мой вопрос очень похож на тот, который опубликован ранее. Я прошел через несколько сообщений для этого, но все же не очень ясен с ответом. Вот почему я отправляя его снова.

Почему Linked HashMap использует двойной LinkedList над Single LinkedList, а заказ также может поддерживаться через Single LinkedList.

В ответах некоторых из предыдущего поста было отмечено, что LinkedHashMap обеспечивает O (1) сложность для удаления, поскольку она имеет предыдущую, а также следующий указатель элемента, но я думаю, что HashMap также O (1) для удаления.

Спасибо,

Answer 1

я думаю, что HashMap также O (1) для удаления

Это правда, но HashMap не должны поддерживать порядок ключей. Поэтому при удалении записи необходимо изменить только небольшой связанный список ведра, из которого была удалена запись (в реализации до Java-версии. В реализации Java 8 используются деревья), что должно занять ожидаемое время O(1).

LinkedHashMap, с другой стороны, должен поддерживать порядок, в котором ключи были добавлены к Карте, что делает с дополнительным связанным списком, который содержит все записи Карты. Поэтому, когда вы удаляете запись, если у вас нет доступа к предыдущей записи в этом большом связанном списке, вам придется перебирать связанный список с самого начала, пока вы его не найдете, что потребует линейного времени.

Вы можете увидеть, что LinkedHashMap делает после удаления записи здесь:

void afterNodeRemoval(Node<K,V> e) { // unlink 
    LinkedHashMap.Entry<K,V> p = 
     (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; 
    p.before = p.after = null; 
    if (b == null) 
     head = a; 
    else 
     b.after = a; 
    if (a == null) 
     tail = b; 
    else 
     a.before = b; 
} 

Это не может быть сделаны в постоянное время с односвязным списком.