Как выполняется removeEldestEntry и какова продолжительность / сложность метода в LinkedHashMap?

Question

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

Я знаю, что все, что нужно сделать removeEldestEntry, это просто вернуть true/false, но затем, когда дело доходит до фактического удаления самой старой записи с карты, может показаться, что во время выполнения будет O(n), что это на самом деле?

Благодарю.

Answer 1

Ява ничего не делает. Реализация этого метода в JDK:

return false;

Это как точка расширения для людей, которые хотят настроить поведение карты в своих подклассах.

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

// Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            //This is the standard HashMap remove, which then finishes by
            //calling Map.Entry#remove() on the removed entry.
            removeEntryForKey(eldest.key);
        }


private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

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

Answer 2

От http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

Если вы отслеживаете самый старый вставленный ключ, тогда удаление будет O(1), иначе O(n).

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