linkedhashmap 订阅
public class LinkedHashMap extends HashMap implements MapMap 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。注意,如果在映射中重新插入 键,则插入顺序不受影响。(如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true,则调用时会将键 k 重新插入到映射 m 中。) 展开全文
public class LinkedHashMap extends HashMap implements MapMap 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。注意,如果在映射中重新插入 键,则插入顺序不受影响。(如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true,则调用时会将键 k 重新插入到映射 m 中。)
信息
外文名
LinkedHashMap
中文名
链表和哈希表实现
LinkedHashMapjava.util.LinkedHashMap
java.lang.Object java.util.AbstractMapjava.util.HashMapjava.util.LinkedHashMapMap 接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。注意,如果在映射中重新插入 键,则插入顺序不受影响。(如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true,则调用时会将键 k 重新插入到映射 m 中。 [1]  )此实现可以让客户避免未指定的、由 HashMap(及 Hashtable)所提供的通常为杂乱无章的排序工作,同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本,而与原映射的实现无关:void foo(Map m) { Map copy = new LinkedHashMap(m); ... } 如果模块通过输入得到一个映射,复制这个映射,然后返回由此副本确定其顺序的结果,这种情况下这项技术特别有用。(客户通常期望返回的内容与其出现的顺序相同。)提供特殊的构造方法来创建链接哈希映射,该哈希映射的迭代顺序就是最后访问其条目的顺序,从近期访问最少到近期访问最多的顺序(访问顺序)。这种映射很适合构建 LRU 缓存。调用 put 或 get 方法将会访问相应的条目(假定调用完成后它还存在)。putAll 方法以指定映射的条目集迭代器提供的键-值映射关系的顺序,为指定映射的每个映射关系生成一个条目访问。任何其他方法均不生成条目访问。特别是,collection 视图上的操作不 影响底层映射的迭代顺序。可以重写 removeEldestEntry(Map.Entry) 方法来实施策略,以便在将新映射关系添加到映射时自动移除旧的映射关系。此类提供所有可选的 Map 操作,并且允许 null 元素。与 HashMap 一样,它可以为基本操作(add、contains 和 remove)提供稳定的性能,假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支,其性能很可能比 HashMap 稍逊一筹,不过这一点例外:LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。HashMap 迭代时间很可能开支较大,因为它所需要的时间与其容量 成比例。链接的哈希映射具有两个影响其性能的参数:初始容量和加载因子。它们的定义与 HashMap 极其相似。要注意,为初始容量选择非常高的值对此类的影响比对 HashMap 要小,因为此类的迭代时间不受容量的影响。注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作,以防止对映射的意外的非同步访问:Map m = Collections.synchronizedMap(new LinkedHashMap(...));结构修改是指添加或删除一个或多个映射关系,或者在按访问顺序链接的哈希映射中影响迭代顺序的任何操作。在按插入顺序链接的哈希映射中,仅更改与映射中已包含键关联的值不是结构修改。在按访问顺序链接的哈希映射中,仅利用 get 查询映射不是结构修改。)Collection(由此类的所有 collection 视图方法所返回)的 iterator 方法返回的迭代器都是快速失败 的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒将来不确定的时间任意发生不确定行为的风险。注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的方式是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。此类是 Java Collections Framework 的成员。
收起全文
精华内容
下载资源
问答
  • LinkedHashMap

    2020-08-24 01:02:52
    文章目录LinkedHashMap详解基本数据结构遍历顺序按照插入顺序遍历顺序按照访问顺序LinkedHashMap实现LRU LinkedHashMap详解 相信大家都知道,HashMap的访问时无序的,如果你想按照插入顺序,访问元素,就必须使用 ...

    LinkedHashMap详解

    相信大家都知道,HashMap的访问时无序的,如果你想按照插入顺序,访问元素,就必须使用

    LinkedHashMap, 下面详细讲述其原理。

    基本数据结构

    LinkedHashMap 的大致数据结构如下图所示

    (链表和哈希表中相同的键值对都是指向同一个对象,区分开来是为了呈现清晰的结构)

    其中双向链表,对元素进行排序,保证按照插入的顺序,访问元素

    遍历顺序按照插入顺序

    LinkedHashMap的链表节点继承了HashMap的节点,而且每个节点都包含了前指针和后指针,所以这里可以看出它是一个双向链表

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

    头指针和尾指针

    /**
    * The head (eldest) of the doubly linked list.
    */
    transient LinkedHashMap.Entry<K,V> head;
    /**
    * The tail (youngest) of the doubly linked list.
    */
    transient LinkedHashMap.Entry<K,V> tail;
    

    在插入key,value键值对后,如果是新的键值对(不存在重复key),会将此键值对作为双链表的尾节点

    调用put方法后,如果是新的键值对,一定会调用newNode方法

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        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);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            	e = p;
            else if (p instanceof TreeNode)
            	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                       		break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                       	 break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                	e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
        	resize();
        afterNodeInsertion(evict);
        return null;
    }
    

    newNode方法, 将新的键值对,作为双链表尾部节点

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    
    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;
        }
    }
    

    遍历顺序按照访问顺序

    final boolean accessOrder;
    

    LinkedHashMap,默认是按照插入顺序,来遍历元素。但是同时也支持按照访问顺序(get方法),来遍历元素

    遍历顺序按照访问顺序,只需要设置accessOrder =true

    按照访问顺序遍历,举个具体的例子

    插入,key为12345的键值对
    执行一次get(2)的操作
    遍历输出的结果为 1 3 4 5 2
    

    如果设置accessOrder为true, LinkedMap在get元素后,会将元素移动至双链表的尾节点

    执行get方法后,会执行afterNodeAcess方法

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

    afterNodeAccess方法。将元素移动至双链表尾节点

    void afterNodeAccess(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;
        }
    }
    

    需要注意的时,put时,发生值覆盖情况,也会支持afterNodeAccess方法

    LinkedHashMap实现LRU

    实现LRU要保证几点

    1. 插入时,新元素在双链表尾部,如果size超过数量,需要删除双链表头部元素(重写removeEldestEntry方法)
    2. 插入时,发生key值重复,即值覆盖情况,需要将相应元素移动至双链表尾部(accessOrder设置为true)
    3. 访问时,需要将相应的元素移动至队列尾部(accessOrder设置为true)
    4. 删除时,哈希表和双链表均需要删除相应元素(满足)

    Leetcode真题https://leetcode-cn.com/problems/lru-cache-lcci/submissions

    import java.util.*;
    
    class ZYMap<K,V> extends LinkedHashMap<K,V> {
      private int cacheSize;
      
      public ZYMap(int cacheSize) {
          super(16,0.75f,true);
          this.cacheSize = cacheSize;
      }
    
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
          return this.size() > cacheSize;
      }
    }
    
    class LRUCache {
        ZYMap map;
        public LRUCache(int capacity) {
            map = new ZYMap<Integer, Integer>(capacity);
        }
        
        public int get(int key) {
            if(map.get(key) == null) return -1;
            else return (int)map.get(key);
        }
        
        public void put(int key, int value) {
            map.put(key,value);
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,185
精华内容 5,274
关键字:

linkedhashmap