LinkedHashMap代码详解(一)-阿里云开发者社区

开发者社区> 人工智能> 正文

LinkedHashMap代码详解(一)

简介: 介绍了LinkedHashMap怎么进行数据的存储和有序链表

HashMap 在遍历map时,数据是无序的,在某些需要按照put顺序遍历时,就用到了LinkedHashMap,LinkedHashMap是HashMap的子类,并且用一条双向链表来存储数据插入的顺序

transient LinkedHashMap.Entry<K,V> head; //链表的头节点
transient LinkedHashMap.Entry<K,V> tail; //链表的尾节点
final boolean accessOrder;               //是否开启lru算法(最活跃的点放在链表头部)

put():
由于LinkedHashMap没有put方法,put操作用的还是HashMap的方法,但是重写了newNode(int hash, K key, V value, Node e) ,afterNodeAccess(Node e),afterNodeInsertion(boolean evict)方法
1 table中不存在相同的key

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

LinkedhashMap重写了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)//如果原尾节点为空,证明链表还没有数据,头节点指向新节点p
            head = p; 
        else {        //链表不为空
            p.before = last; 
            last.after = p;//原尾节点建立双向链接
        }
    }

2 table数组中存在相同的key

           if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

发生了节点数据操作(value替换),如果开启了LRU(accessOrder=true),则将修改的节点放入链表尾部,HashMap.afterNodeAccess() 为空函数
LinkedHashMap overwirte了该方法

      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;
              
            /**重写上面的赋值操作
            LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e;
            LinkedHashMap.Entry<K,V> b(befor) = p.before;
            LinkedHashMap.Entry<K,V> a(after) = p.after;           
            **/
            p.after = null; //将修改的节点after置为null
            if (b == null)  //如果b==null  证明e是头结点
                head = a;  //将链表头结点指向 e.next
            else            //e不是头结点
                b.after = a;  // e.befor.after = e.after
                             // e节点的上一个节点的next指向e的下一个节点,移除e
            if (a != null)   //如果e的下一个节点不为空
                a.before = b;//e.after.befor= e.after
                             // e节点的下一个节点的befor指向e的上一个节点,双向链表的反向箭头
            else             // a == null e是尾部节点
                last = b;    //last指向e的上一个节点
            if (last == null) //如果 last== null 证明 只有一个节点
                head = p;      //头部尾部都指向该节点
            else {              // p不是头节点
                p.before = last; //将p放在链表尾部 
                last.after = p;
            }
            tail = p;
            ++modCount;        //map操作数+1,(重新赋值且开启LRU,modCount会两次+1)
        }
    }

3 在执行完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;
    }

evict 在hashMap中默认为true,LinkedHashMap.removeEldestEntry ()默认返回false,
该方法的yongfasj用法是 配合LRU算法,自定义Class继承LinkedHashMap方法并重写removeEldestEntry 方法,
在特定条件下返回true,移除链表中最左侧的节点
可以使用该特性进行缓存创建,保留最近活跃的数据,开启LRU需要将开头提到的accessOrder 置为true

该参数只能在LinkedHashMap new时指定,需要同时指定扩展因子loadFactor 默认为0.75f

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

get():
LinkedHashMap get方法,可以看到 和hashMap是一致的,只是加了accessOrder 判断,开启LRU后,将获取的数据放在链表的最右侧,提高该节点的活跃程度

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章