Карта анализа коллекции Java - эта карта имеет порядок (LinkedHashMap и TreeMap)

Java задняя часть алгоритм
Карта анализа коллекции Java - эта карта имеет порядок (LinkedHashMap и TreeMap)

В предыдущей статье уже было проанализированоHashMap, по его реализации известны его неупорядоченные свойства элементов. Сегодня давайте проанализируем следующие два, которые могут гарантировать порядок элементовMap- Гарантированный порядок размещенияLinkedHashMapи настраиваемая сортировкаTreeMap, чтобы увидеть, как достигается порядок.

Примечание. Эта статья основана на jdk_1.8.0_162.

Map家族谱

LinkedHashMap

внутренняя структура

Обзор

​LinkedHashMapунаследовано отHashMap, или переопределить или реализовать некоторые методы в родительском классе, что в определенной степени воплощает полиморфизм.LinkedHashMapПоддерживая дополнительный связанный список порядка вставки, гарантируется порядок доступа к элементам. В то же время имуществоaccessOrderВы можете установить порядок элементов настройки для легкой реализацииLRUалгоритм.

LinkedList = HashMap + LinkedList

основные члены

Основные участники следующие:

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    //元素头节点
    transient LinkedHashMap.Entry<K,V> head;
    //元素尾节点
    transient LinkedHashMap.Entry<K,V> tail;
    //是否维护访问顺序，true 则按访问顺序，false 则按插入顺序
    final boolean accessOrder;
}

в,EntryСтруктура следующая, унаследованная отHashMap.Nodeи поддерживает информацию об узле до и после элемента:

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);
    }
}

Ключевой метод скрытой точки родительского класса

​LinkedHashMapунаследовано отHashMap, базовая реализация повторно использует родительский класс, подробнее см.:Карта анализа коллекции Java — начиная с HashMap.LinkedHashMapв основном реализованоHashMapВ нем определены, но не реализованы три метода:

void afterNodeAccess(Node<K,V> p) { }

void afterNodeInsertion(boolean evict) { }

void afterNodeRemoval(Node<K,V> p) { }

AfternoDeaCCess метод

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // accessOrder 为 true ，且该元素不是尾节点
    if (accessOrder && (last = tail) != e) {
        // p 是当前节点 ，b 是前一个节点 ，a 是后一个节点
        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;
    }
}

Этот методputиgetЗвонил во время работы. еслиaccessOrder == true,существуетputПосле этого, даже если доступ к элементу будет осуществлен, связанный список будет обновлен, и элемент будет помещен в конец связанного списка.

метод afterNodeInsertion

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);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

Это реализацияLRUАлгоритм ключевым местом для достижения удаления правила, необходимостьaccessOrderУстановить какtrue.

метод afterNodeRemoval

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;
}

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

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

Метод доступа к элементу

положить метод

​putМетод не переопределяется, он просто реализуетсяafterNodeInsertionПосле этого записывается порядок вставки элементов. Если вам интересно, вы можете вернуться к предыдущемуHashMapАнализируйте статьи.

получить метод

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //设置了访问顺序，则维护之
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

​getВ операции нет ничего особенного, иHashMapПолучите узел элемента таким же образом. если установленоaccessOrder, порядок связанного списка сохраняется.

Алгоритм LRU

С помощью приведенного выше анализа мы можем использоватьLinkedHashMapОчень легко достичьLRUалгоритм.

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

    // 最大容量
    private Integer maxSize;

    public LRUCache(Integer maxSize, int initCapacity, float loadFactor) {
        super(initCapacity, loadFactor, true);
        this.maxSize = maxSize;
    }

    public LRUCache(int maxSize) {
        this(maxSize, 16, 0.75f);
    }

    public LRUCache() {
        this(Integer.MAX_VALUE);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > maxSize;
    }

    public static void main(String[] args) {
        Map<String, Integer> cache = new LRUCache<>(3);
        cache.put("aaa", 1);
        cache.put("bbb", 1);
        System.out.println(cache);
        cache.put("ccc", 1);
        cache.get("aaa");
        System.out.println(cache);
        cache.put("ddd", 1);
        System.out.println(cache);
    }
}

Результаты операции следующие: видно, что порядок элементов при доступе будет скорректирован, а также будут отсеяны наименее часто используемые данные.

{aaa=1, bbb=1}
{bbb=1, ccc=1, aaa=1}
{ccc=1, aaa=1, ddd=1}

TreeMap

внутренняя структура

Обзор

​TreeMapунаследовано отAbstractMap, выполненоNavigableMap, в соответствии с определяемым пользователем компаратором илиKey.compareToВ качестве сортировки, и используйте красно-черное дерево для реализации.

основные члены

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    //比较器，用于排序，如果无比较器则使用 key 的比较规则来排序
    private final Comparator<? super K> comparator;
    //存放数据的节点entry, root 是要节点
    private transient Entry<K,V> root;
    private transient int size = 0;
    private transient int modCount = 0;
}

​TreeMapСортировка сначала смотрит на компаратор, если компаратора нет, он будет использоваться сноваKeyПравила сравнения для сортировки будут описаны ниже.EntryДанные узла красно-черного дерева сохраняются, а структура данных следующая:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

Узлы содержат пары ключ-значение, родительские узлы, левые дочерние узлы, правые дочерние узлы и информацию, связанную с красно-черным деревом. Эта статья изучает толькоTreeMapРеализация красно-черного дерева специально не изучает соответствующие знания.

Конструктор

//默认构造器，比较器初始化为空，但是要求Key实现Comparable接口，不然无法put数据
public TreeMap() {
    comparator = null;
}

//带有比较器的构造器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

//带有集合元素的构造器，但是如果不是SortedMap，
//且Key没实现Comparable，仍然会报错，因为会调用put方法
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

//带有集合元素的构造器，会使用sortedMap的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

метод доступа к элементу

положить метод

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        //校验基本条件，即必须可比较
        compare(key, key);
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    
    //比较结果，即应该在父节点的左子节点还是或子节点
    int cmp;
    //父节点到底在哪
    Entry<K,V> parent;
    
    //将 Comparator 和 Comparable 进行分开操作，可见 Comparator 优先级高
    Comparator<? super K> cpr = comparator;
    //如果有比较器 Comparator
    if (cpr != null) {
        //循环确定父节点的位置，同时确定自己在左子节点还是右子节点
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            //划重点，这里是根据 compare 方法来判断是不是同一个元素
            //而不是 hashcode 和 equals
            else
                return t.setValue(value);
        } while (t != null);
    }
    //这里只能是无Comparator而有Comparable的了
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        //同Comparator
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
    } while (t != null);
    }
    //新建节点插入到正确位置
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    //红黑树处理
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

//compare 方法，会进行校验，要求要么传递比较器，要么 Key 实现 Comparable
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

отputметод, видно, что дляTreeMapС точки зрения, при использовании либоKeyДостигнутоComparable, или прошел вComparator,Это очень важно. В то же время в этих двух случаях в основном будут обрабатываться другие серии операций. в то же время,Comparatorприоритет выше, чемComparableиз.

получить метод

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

//根据key找到对应的树节点
final Entry<K,V> getEntry(Object key) {
    // 传入了Comparator的，根据比较器来找
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    //从要节点开始树查找，compareTo的结果为0是目标节点
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

//根据Comparator来找树节点
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        //从要节点开始进行树查找，compare的结果为0是目标节点
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

​getМетод снова подтверждается.Comparatorприоритет выше, чемComparableиз.

метод удаления

public V remove(Object key) {
    //找至对应的树节点
    Entry<K,V> p = getEntry(key);
    //key不存在则返回null
    if (p == null)
        return null;
    V oldValue = p.value;
    //删除节点，维护节点关系，并做红黑树处理
    deleteEntry(p);
    //返回key对应的value
    return oldValue;
}

Суммировать

  • LinkedHashMapФактическиHashMap + LinkedList
  • LinkedHashMapможно использовать для реализацииLRUалгоритм
  • TreeMapСортировка в соответствии с заданным пользователем сопоставлением и использование红黑树Достигать
  • TreeMapизKeyНе обнуляемый, потому что компаратор должен быть вызван илиKeyизcompareToметод
  • TreeMapОпределить, основан ли один и тот же элемент наComparatorилиComparable, вместоhashcodeиequals
  • TreeMapЕсли компаратор определен,Keyне могут быть реализованыComparableинтерфейс
  • TreeMapПравила компаратора имеют приоритет надKeyправила сравнения для
  • Автор этой статьи: DomKing
  • Ссылка на эту статью: blog.PR code.org/2018/03/J av…
  • Уведомление об авторских правах:Все статьи в этом блоге, если не указано иное, используютCC BY-NC-SA 3.0соглашение. Пожалуйста, укажите источник!
Категории