Использование двусвязного списка в LinkedHashMap поверх единого Linked List

Question

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

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

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

Спасибо,

Answer 1

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

Это правда, но HashMap не должен поддерживать порядок ключей. Следовательно, при удалении записи необходимо изменить только небольшой связанный список сегмента, из которого удалена запись (в реализации до Java 8. В реализации 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;
}

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