В этой статье мы начали анализировать исходный код LinkedHashmap. LinkedHashmap наследует HashMap, что означает, что LinkedHashmap расширен на основе HashMap. Поэтому, прежде чем посмотреть на исходный код LinkedHashmap, читатели должны понимать исходный код HashMap. Вы можете проверить введение моей предыдущей статьи «Серия коллекций Java [3] ---- HashMap Исходного кода». Пока у вас есть глубокое понимание принципа реализации HashMap, а затем взглянуть на исходные коды LinkedHashmap, Hashset и LinkedHashset - все это очень просты. Поэтому читатели должны быть терпеливыми и изучать исходный код HashMap. Это хороший бизнес, чтобы купить один, получите три бесплатных. При анализе исходного кода HashMap ранее я использовал, ориентированный на проблемный анализ исходного кода, чтобы я не анализировал его случайным образом, как безголов, и читатели также могли более глубоко понимать проблему. В этой статье я решил использовать этот метод для анализа LinkedHashmap.
1. Какая структура используется внутри LinkedHashmap?
Как вы можете видеть, поскольку LinkedHashmap наследует от HashMap, внутри LinkedHashmap все еще есть хэш -таблица, но LinkedHashmap переписал запись и добавил две переменные элемента в исходную запись HashMap, а также предыдущую ссылку на узел и ссылку на преемник узла. Таким образом, все узлы связаны вместе, чтобы сформировать двусторонний связанный список. При получении элементов просто перейдите по двустороннему связанному списку напрямую. Давайте посмотрим, как выглядит реализация входа LinkedHashmap.
Частная статическая запись класса <K, v> extends hashmap.entry <k, v> {// Ссылка на предыдущий узел текущего узла в двунаправленной связанной записи списка <K, v> до; // Ссылка на последующий узел текущего узла в двунаправленной связанной записи списка <K, V> после; Inpit (int hash, k key, v value, hashmap.entry <k, v> next) {super (hash, key, value, next); } // Удалить этот узел из двунаправленного связанного списка private void remod () {до.fter = после; после. } // Вставить текущий узел в существующий узел в двунаправленный связанный список Private void AddBefore (intry <K, V> существующий // Ссылка на предыдущий узел текущего узла указывает на предыдущий узел данного узла до = существует // Ссылка на следующий узел данного узла указывает на текущий узел до. After = this; // Ссылка на предыдущий узел данного узла указывает на текущий узел After.before = this; } // Сортируется в порядке доступа, записывайте каждый раз, когда операция получается void recordaccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // Если отсортировано в порядке доступа, если (lm.accessorder) {lm.modcount ++; // Сначала удалить себя из двунаправленного связанного списка; // Поместите себя в хвост двунаправленного связанного списка AddBefore (Lm.Header); }} void recordRemoval (hashmap <k, v> m) {rement (); }}2. Как LinkedHashmap реализует сортировку в заказе вставки?
// Метод, который будет вызван в методе POT родительского класса void AddEntry (int hash, k -ключ, v Значение, int bucketIndex) {// Вызов метода добавления родительского класса Super.addentry (хэш, ключ, значение, bucketIndex); // Следующая операция удобна для реализации кэша LRU. Если емкость кэша недостаточна, удалите самую старую запись элемента <K, V> Olderly = header.fter; if (removeEldestentry (aldest)) {removerEntryForkey (eldest.key); }} // Метод void createentry (int hash, k -ключ, v Значение, int bucketIndex) {// Сначала получить хэшмап ввода hashmap.entry <k, v> old = table [bucketindex]; // Завернуть его в собственную запись LinkedHashmap <K, v> e = новая запись <> (хэш, ключ, значение, старое); Таблица [BucketIndex] = E; // вставить текущий узел в хвост двунаправленного связанного списка e.addbefore (заголовок); размер ++;}LinkedHashmap переопределяет методы AddEntry и Createentry Hashmap своего родительского класса. Если вы захотите вставить пару ключевых значений, в первую очередь будет называться метод POT его родительского класса Hashmap. В методе PUT мы проверим, существует ли соответствующий ключ в хэш -таблице. Если он существует, просто замените его значение напрямую. Если его не существует, вызовите метод добавления, чтобы создать новую запись. Обратите внимание, что в настоящее время называется собственным методом добавления LinkedHashmap. Мы видим приведенный выше код. В дополнение к вызову метода Addeldestentry в родительском классе, этот Addeldestentry также вызовет removeldestentry, чтобы удалить самый старый элемент. Эта операция в основном для реализации алгоритма LRU, который будет обсуждаться ниже. Мы видим, что LinkedHashmap также переписывает метод Createentry. Когда вы хотите создать новую запись, этот метод будет вызван. После каждого раз, когда запись помещается в хэш -таблицу, метод AddBefore будет вызван для вставки текущего узла в хвост связанного списка двунаправленного связанного списка. Таким образом, двунаправленный связанный список записывает порядок каждого вставленного узла. При получении элементов просто пересекайте связанный список двунаправленных. На следующем рисунке показана операция каждого вызова, чтобы добавить перед добавлением. Поскольку это двунаправленный связанный список, прежде чем вставить текущий узел в узел головного узла, он фактически вставляет текущий узел в хвост связанного списка двунаправленного связанного списка.
3. Как использовать LinkedHashmap для реализации кэша LRU?
Мы знаем, что реализация кэша зависит от памяти компьютера, а ресурсы памяти весьма ограничены, и невозможно хранить элементы без ограничений. Поэтому нам нужно надлежащим образом удалить некоторые элементы, когда емкость недостаточна. Итак, какой элемент лучше удалить? Идея алгоритма LRU состоит в том, что если к данным доступ к данным был доступен недавно, шансы на доступ к будущему также выше. Таким образом, мы можем удалить данные, которые не часто доступны. Затем давайте посмотрим, как LinkedHashmap реализует механизм LRU.
открытый класс LinkedHashmap <K, V> extends HashMap <K, V> реализует карту <K, V> {// Showlly Linked List Header Private Transient Intpring <K, V> заголовок; // Сортировать частный окончательный логический доход в порядке доступа; ... public linkedHashmap (int initialCapacity, float LoadFactor, Boolean Accessord) {Super (initialCapacity, LoadFactor); this.accessorder = accessorde; } // Получить значение в соответствии с ключом public v get (object key) {// вызов метода родительского класса, чтобы получить соответствующую запись в записи <K, v> e = (inpit <k, v>) getEntry (key); if (e == null) {return null; } // Если он сортируется в порядке доступа, узел после каждого использования будет размещен в конце двунаправленного связанного списка e.recordaccess (this); вернуть E.value; } частная статическая запись класса <K, v> extends hashmap.entry <k, v> {... // Вставить текущий узел в переднюю часть существующего узла в двунаправленном связанном списке Private void Addbefore (int <K, v> существующий элемент) {// Справочник следующего узла текущего узла на данный Node после = существующий) {/ Справочник следующего узла текущего узла на заданный Node после = существующий); // Ссылка на предыдущий узел текущего узла указывает на предыдущий узел данного узла до = существует // Ссылка на следующий узел данного узла указывает на текущий узел до. After = this; // Ссылка на предыдущий узел данного узла указывает на текущий узел After.before = this; } // Сортируется в порядке доступа, записывайте каждый раз, когда операция void recordccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // Если отсортировано в порядке доступа, если (lm.accessorder) {lm.modcount ++; // Сначала удалить себя из двунаправленного связанного списка; // Поместите себя в хвост двунаправленного связанного списка AddBefore (Lm.Header); }} ...} // Этот метод будет вызван в родительском классе PUT Method void AddEntry (int hash, k -ключ, v Значение, int bucketIndex) {// Рассчитать метод аддентрического класса родительского класса Super.Addentry (хэш, ключ, значение, bucketIndex); // Следующая операция удобна для реализации кэша LRU. Если емкость кэша недостаточна, удалите самую старую запись элемента <K, V> Olderly = header.fter; if (removeEldestentry (aldest)) {removeeldestforkey (eldest.key); }} // Где удалить самый старый элемент? Этот метод предназначен для перезаписания подклассами, защищенными логическими, removeEldestentry (map.Entry <k, v> пожилые люди) {return false; }}Чтобы быть более интуитивно понятным, я пропустил какой -то нерелевантный код в коде, размещенном выше. Мы видим, что LinkedHashmap имеет доход с переменной члена, который записывает, необходимо ли его отсортировать в порядке доступа. Он предоставляет конструктор, который может указать значение самого доклада. Каждый раз, когда вы называете метод GET, чтобы получить элемент, называется E.RecordAccess (это), который будет перемещать текущий узел в конце двунаправленного связанного списка. Теперь мы знаем, что если доход верно, то каждый раз, когда мы получаем элемент, мы перемещаем этот элемент в конце списка двунаправленных ссылок. Цель этого шага состоит в том, чтобы отличить наиболее часто используемые элементы от тех, которые не часто используются, и часто используемые элементы помещаются в конце, и на голове помещаются менее часто используемые элементы. Давайте вернемся к вышеуказанному коду и увидим, что каждый раз, когда называется метод добавления, мы определим, должен ли самый старый элемент быть удаленным. Логика суждения реализована с помощью RemoveEldestentry, которая предназначена для переопределения подклассами и переписывает логику внутри. Обратите внимание, что с тех пор, как недавно посещаемые узлы перемещаются в хвост связанного списка двунаправленного связанного списка, самый старый узел выводится из главы двунаправленного связанного списка для удаления. Следующий пример реализует простой кэш LRU.
открытый класс LRUMAP <K, V> расширяет LinkedHashmap <K, V> {Private Int емкость; LRUMAP (int емкость) {// вызов конструктора родительского класса, установлен для сортировки в заказе доступа Super (емкость, 1F, true); this.capacity = емкость; } @Override public boolean removeEldEStentry (map.Entry <k, v> пожилой) {// Когда пара ключевых значений превышает или равна емкости хэш-таблицы. Возврат this.size ()> = емкость; } public static void main (string [] args) {lrumap <integer, string> map = new lrumap <integer, string> (4); map.put (1, "a"); map.put (2, "b"); map.put (3, "c"); System.out.println ("Оригинальная коллекция:" + map); Строка s = map.get (2); System.out.println ("get element:" + map); map.put (4, "D"); System.out.println ("После вставки:" + map); }}Результаты следующие:
ПРИМЕЧАНИЕ. Все вышеперечисленные анализы основаны на JDK1.7, и будут различия между различными версиями, читатели должны обратить внимание.
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.