Я слышал, что вы не понимаете LinkedHashMap в Java, это смешно.

Java
Я слышал, что вы не понимаете LinkedHashMap в Java, это смешно.

Сначала посмотрите, а потом лайкните, дайте себе время подумать, поиск в WeChat [Тихий король 2] Обратите внимание на этого красивого программиста, который делает вид, что полагается на талант. Эта статья GitHub github.com/itwangerОн был включен, а также есть вопросы для интервью, которые я тщательно подготовил для вас.

Привет одноклассники, вы еще помните?HashMapЭто один? Я сам чувствую, что написание очень хорошее, оно легкое для понимания и глубоко уходит в исходный код, оно действительно проанализировано тщательно, четко и ясно. (Случайно добавил три идиомы?) HashMap хорош везде, действительно, пока вы хотите использовать пары ключ-значение, вы должны думать об этом в первый раз.

Но, как говорится, «никто не идеален без мужчины», и HashMap не исключение. Есть требование, которое он не может удовлетворить: если нам нужен набор пар ключ-значение, расположенных в порядке вставки, то HashMap бессилен. Потому что для повышения эффективности поиска HashMap выполняет алгоритм хэширования ключа при вставке, из-за чего вставленные элементы оказываются не в порядке.

Студенты, которые не понимают этот момент, вы можете вернуться кHashMapТот, посмотри на меня справаput()объяснение метода.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    // ①、数组 table 为 null 时，调用 resize 方法创建默认大小的数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // ②、计算下标，如果该位置上没有值，则填充
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
}

эта формулаi = (n - 1) & hashВычисленное значение не вставляет в массив пару ключ-значение по упорядоченным индексам 0, 1, 2, 3, 4, 5, а имеет некоторую случайность.

Этот LinkedHashMap появился для этого требования. LinkedHashMap наследует HashMap, поэтому у HashMap есть функции пар ключ-значение, у него тоже есть.

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>{}

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

static class Entry<K,V> extends HashMap.Node<K,V> {
    LinkedHashMap.Entry<K,V> before, after;
    Entry(int hash, K key, V value, HashMap.Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Что касается двусвязного списка, учащиеся могут оглянуться на то, что я написал.LinkedListЭта статья будет очень полезна для понимания LinkedHashMap в этой статье.

Прежде чем продолжить ниже, я выложу картинку для немного веселья - посмотрите на мое сердце. В заголовке статьи UUID использовались слова «нелепо» и «вы», и я увидел такое счастливое сообщение ниже.

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

01. Порядок размещения

существуетHashMapВ той статье я объяснил один момент, не знаю, помнят ли его студенты, то есть null будет вставлен в первую позицию HashMap.

Map<String, String> hashMap = new HashMap<>();
hashMap.put("沉", "沉默王二");
hashMap.put("默", "沉默王二");
hashMap.put("王", "沉默王二");
hashMap.put("二", "沉默王二");
hashMap.put(null, null);

for (String key : hashMap.keySet()) {
    System.out.println(key + " : " + hashMap.get(key));
}

Результат:

null : null
默 : 沉默王二
沉 : 沉默王二
王 : 沉默王二
二 : 沉默王二

Хотя последний бит нуля был введен, он оказался на первом месте при обходе вывода.

Затем взгляните на LinkedHashMap для сравнения.

Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("沉", "沉默王二");
linkedHashMap.put("默", "沉默王二");
linkedHashMap.put("王", "沉默王二");
linkedHashMap.put("二", "沉默王二");
linkedHashMap.put(null, null);

for (String key : linkedHashMap.keySet()) {
    System.out.println(key + " : " + linkedHashMap.get(key));
}

Результат:

沉 : 沉默王二
默 : 沉默王二
王 : 沉默王二
二 : 沉默王二
null : null

null вставляется в последний бит, выводится в последний бит.

Выходной результат может снова доказать, что HashMap неупорядочен, и LinkedHashMap может поддерживать порядок вставки.

Так как же LinkedHashMap делает это? Я считаю, что мои одноклассники, как и я, очень хотят знать, почему.

Чтобы разобраться, нужно покопаться в исходном коде LinkedHashMap. LinkedHashMap не переопределяет HashMap.put()метод, но приоритетныйput()Внутренний метод, который метод должен вызыватьnewNode().

HashMap.Node<K,V> newNode(int hash, K key, V value, HashMap.Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

Как упоминалось ранее, LinkedHashMap.Entry наследует HashMap.Node и добавляет два поля до и после.

Что ж, давайте посмотримlinkNodeLast()метод:

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

Видите, когда LinkedHashMap добавит первый элемент, он назначит заголовок первому элементу, а когда будет добавлен второй элемент, он назначит до второго элемента первому элементу, а первому элементу будет присвоен первый элемент. ко второму элементу.

Это гарантирует, что пары ключ-значение находятся в порядке вставки, понимаете?

Примечание. Я использую JDK версии 14..

02. Последовательность доступа

LinkedHashMap поддерживает не только порядок вставки, но и порядок доступа. доступ включает звонкиget()метод,remove()Методы иput()метод.

Чтобы поддерживать порядок доступа, нам нужно указать три параметра при объявлении LinkedHashMap.

LinkedHashMap<String, String> map = new LinkedHashMap<>(16, .75f, true);

Первый параметр и второй параметр см.HashMapСтуденты должны быть знакомы с ним, имея в виду начальную вместимость и коэффициент загрузки.

Если третий параметр имеет значение true, это означает, что LinkedHashMap должен поддерживать порядок доступа, в противном случае поддерживать порядок вставки. Значение по умолчанию — ложь.

Map<String, String> linkedHashMap = new LinkedHashMap<>(16, .75f, true);
linkedHashMap.put("沉", "沉默王二");
linkedHashMap.put("默", "沉默王二");
linkedHashMap.put("王", "沉默王二");
linkedHashMap.put("二", "沉默王二");

System.out.println(linkedHashMap);

linkedHashMap.get("默");
System.out.println(linkedHashMap);

linkedHashMap.get("王");
System.out.println(linkedHashMap);

Результат выглядит следующим образом:

{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二}
{沉=沉默王二, 王=沉默王二, 二=沉默王二, 默=沉默王二}
{沉=沉默王二, 二=沉默王二, 默=沉默王二, 王=沉默王二}

когда мы используемget()После того, как метод обращается к элементу, ключ которого «молчит», в выходном результате默=沉默王二В конце, когда мы обращаемся к элементу ключа «Король», в результате вывода王=沉默王二в конце,默=沉默王二на предпоследней позиции.

То есть в голову помещается наименее часто используемый, что интересно. Где интерес?

Мы можем использовать LinkedHashMap для реализации кеша LRU.LRU — это аббревиатура наименее недавно использованных, которые используются реже всего.Это широко используемый алгоритм замены страниц, который выбирает самые последние неиспользуемые страницы для исключения.

public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_ENTRIES = 5;

    public MyLinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor, accessOrder);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

}

MyLinkedHashMap — это пользовательский класс, который наследует LinkedHashMap и переопределяетremoveEldestEntry()Метод. Сделайте так, чтобы карта содержала до 5 элементов и отбрасывала ее, если она превышала.

Давайте проверим это.

MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("沉", "沉默王二");
map.put("默", "沉默王二");
map.put("王", "沉默王二");
map.put("二", "沉默王二");
map.put("一枚有趣的程序员", "一枚有趣的程序员");

System.out.println(map);

map.put("一枚有颜值的程序员", "一枚有颜值的程序员");
System.out.println(map);

map.put("一枚有才华的程序员","一枚有才华的程序员");
System.out.println(map);

Результат выглядит следующим образом:

{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员}
{默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员}
{王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员, 一枚有才华的程序员=一枚有才华的程序员}

沉=沉默王二а также默=沉默王二ликвидировались по очереди.

Если вы получаете элемент с ключом «молчаливый» перед тем, как поставить «талантливый программист»:

MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("沉", "沉默王二");
map.put("默", "沉默王二");
map.put("王", "沉默王二");
map.put("二", "沉默王二");
map.put("一枚有趣的程序员", "一枚有趣的程序员");

System.out.println(map);

map.put("一枚有颜值的程序员", "一枚有颜值的程序员");
System.out.println(map);

map.get("默");
map.put("一枚有才华的程序员","一枚有才华的程序员");
System.out.println(map);

Тогда выход изменится, не так ли?

{沉=沉默王二, 默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员}
{默=沉默王二, 王=沉默王二, 二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员}
{二=沉默王二, 一枚有趣的程序员=一枚有趣的程序员, 一枚有颜值的程序员=一枚有颜值的程序员, 默=沉默王二, 一枚有才华的程序员=一枚有才华的程序员}

沉=沉默王二а также王=沉默王二Был ликвидирован.

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

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

afterNodeAccess()буду звонитьget()называется метод,afterNodeInsertion()буду звонитьput()называется метод,afterNodeRemoval()буду звонитьremove()метод называется.

я пришел сafterNodeAccess()Возьмем пример.

void afterNodeAccess(HashMap.Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

Какой элемент ставится последним. Понятно?

Тогда студенты также могут захотеть узнать, почему LinkedHashMap может реализовать LRU-кеш и исключить элемент, к которому реже всего обращаются?

При вставке элемента необходимо вызватьput()метод, который в конечном итоге вызоветafterNodeInsertion()метод, который переопределяется LinkedHashMap.

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry()Метод определит, превышает ли первый элемент максимальный допустимый диапазон, и если да, то вызоветremoveNode()Метод удаляет наименее часто используемый элемент.

03. Наконец

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

Это тоже невозможно, правильно, если хочешь носить корону, ты должен нести ее вес. Поскольку вы хотите поддерживать порядок элементов, всегда есть цена, которую нужно заплатить.

Затем эта статья резко обрывается здесь.Если студенты считают, что они еще не закончены, пожалуйста, оставьте сообщение и сообщите мне. (Случайно кинув три идиомы в конце статьи, там немного культурного наследия, да?)

Я Тихий Король Эр, красивый программист, который делает вид, что полагается на свой талант.Подпишитесь, чтобы повысить эффективность обучения, не забудьте три раза подряд ах, лайк, избранное, оставить сообщение, я не выбираю, Олли дает 🌹.

Примечание. Если в статье есть какие-либо проблемы, пожалуйста, исправьте их.

Если вы считаете, что статья полезна для вас, добро пожаловать в поиск WeChat »Тихий король 2"Прочтите в первый раз, ответьте на ключевое слово"новичек«Вы можете бесплатно получить версию 2.0 «Java Xiaobai от новичка до самонадеянного» с более чем 40 000 слов моей печени; эта статьяGitHub github.com/itwangerОн был записан, добро пожаловать в звезду.

Категории