Интервьюер: Как реализовать LRU с LinkedHashMap

Java

В прошлой статье был проанализирован принцип HashMap. Некоторые пользователи сети оставили сообщение и хотели увидеть анализ LinkedHashMap. Сегодня он здесь.

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

LinkedHashMap结构

На картинке выше я нарисовал только связанный список, на самом деле узлы красно-черного дерева одинаковые, но типы узлов разные.

То есть, когда мы просматриваем LinkedHashMap, мы проходим от узла, на который указывает головной указатель, к узлу, на который указывает хвост.

исходный код

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

    // 双向链表头节点
    transient LinkedHashMap.Entry<K,V> head;

    // 双向链表尾节点
    transient LinkedHashMap.Entry<K,V> tail;

    // 指定遍历LinkedHashMap的顺序,true表示按照访问顺序,false表示按照插入顺序，默认为false
    final boolean accessOrder;
  }

}

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

public LinkedHashMap(int initialCapacity,float loadFactor,
                   boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
}

Когда accessOrder=true, что означает вывод порядка доступа? Взгляните на следующий фрагмент кода

LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(8, 0.75f, true);

map.put(1, 1);
map.put(2, 2);
map.put(3, 3);

map.get(2);

System.out.println(map);

Выход

{1=1, 3=3, 2=2}

Видно, что полученные данные помещаются в конец двусвязного списка, то есть сортируются по времени доступа, что и является смыслом порядка доступа.

При вставке LinkedHashMap перезаписывает методы newNode и newTreeNode HashMap и обновляет отношение указателей двусвязного списка внутри метода.

При этом при вставке вызываются метод afterNodeAccess() и метод afterNodeInsertion().В HashMap эти два метода являются пустыми реализациями, а в LinkedHashMap есть конкретные реализации.Эти два метода также специально используются для обработки обратного вызова LinkedHashMap .

В методе afterNodeAccess(), если accessOrder=true, узел будет перемещен в конец двусвязного списка. Когда мы вызываем метод map.get(), если accessOrder=true, этот метод также будет вызываться, поэтому элементы, к которым осуществляется доступ, перемещаются в конец связанного списка при выводе порядка доступа.

Далее, давайте взглянем на реализацию afterNodeInsertion().

// evict如果为false，则表处于创建模式,当我们new HashMap(Map map)的时候就处于创建模式
void afterNodeInsertion(boolean evict) { // possibly remove eldest
  LinkedHashMap.Entry<K,V> first;

  // removeEldestEntry 总是返回false,所以下面的代码不会执行。
  if (evict && (first = head) != null && removeEldestEntry(first)) {
      K key = first.key;
      removeNode(hash(key), key, null, false, true);
  }
}

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

public class LRUCache<K,V> extends LinkedHashMap<K,V> {
    
  private int cacheSize;
  
  public LRUCache(int cacheSize) {
      super(16,0.75f,true);
      this.cacheSize = cacheSize;
  }

  /**
   * 判断元素个数是否超过缓存容量
   */
  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
      return size() > cacheSize;
  }
}

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

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

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

Категории