精华内容
下载资源
问答
  • 1概述LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时...在实现上,LinkedHashMap 很多方法直接继承自 HashMap,仅为维护双向链表覆写了部分方法。所以,要看懂 L...

    fa72f89ca37df958b27d1057e816f234.png

    1概述

    LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外,LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下,该特性很有用,比如缓存。在实现上,LinkedHashMap 很多方法直接继承自 HashMap,仅为维护双向链表覆写了部分方法。所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码。

    2.1 LinkedHashMap的数据结构

    781e2af54d152049a11ab2bf98aafb0d.png

    可以从上图中看到,LinkedHashMap数据结构相比较于HashMap来说,添加了双向指针,分别指向前一个节点——before和后一个节点——after,从而将所有的节点已链表的形式串联一起来,从名字上来看LinkedHashMap与HashMap有一定的联系,实际上也确实是这样,LinkedHashMap继承了HashMap,重写了HashMap的一部分方法,从而加入了链表的实现。让我们来看一下它们的继承关系。

    2.2 LinkedHashMap的继承关系

    2.2.1 Entry的继承关系

    616024bd470ac364b31b06dd0c03b86e.png

    核心数据结构中,lhm在自己的Node结构中,加入了before与after节点,表明 这是一个双向链表,那么如果尾结点的after指向了head,head的before指向了tail节点,那么这就是一个循环链表,通过代码发现并没有这么说,表明这仅仅是一个双向链表;与Node中的next不同,next描述的是经过hash后,同一个桶中(即下标)的链表节点关系,这也说明,进行节点相关操作的时候,需要注意(也没什么注意的,因为在父类中,已经对next节点进行了调整,子类只要解决自己的事就可以了,这也是为什么用继承的原因了)

    3LinkedHashMap源码解析

    本节我们将结合HashMap的部分源码一起分析一下LinkedHashMap。

    c3ae7e9dce812791c25c68af7638f398.png

    构造方法

    跟HashMap类似的构造方法这里就不一一赘述了,里面唯一的区别就是添加了前面提到的accessOrder,默认赋值为false——按照插入顺序来排列,这里主要说明一下不同的构造方法。

    //多了一个 accessOrder的参数,用来指定按照LRU排列方式还是顺序插入的排序方式
    public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
       super(initialCapacity, loadFactor);
       this.accessOrder = accessOrder;
     }

    4 LinkedHashMap的get()方法

    public V get(Object key) {
      Node<K,V> e;
      //调用HashMap的getNode的方法,详见上一篇HashMap源码解析
      if ((e = getNode(hash(key), key)) == null)
        return null;
      //在取值后对参数accessOrder进行判断,如果为true,执行afterNodeAccess
      if (accessOrder)
        afterNodeAccess(e);
      return e.value;
    }

    从上面的代码可以看到,LinkedHashMap的get方法,调用HashMap的getNode方法后,对accessOrder的值进行了判断,我们之前提到:

    accessOrder为true则表示按照基于访问的顺序来排列,意思就是最近使用的entry,放在链表的最末尾

    由此可见,afterNodeAccess(e)就是基于访问的顺序排列的关键,让我们来看一下它的代码:

    //此函数执行的效果就是将最近使用的Node,放在链表的最末尾
    void afterNodeAccess(Node<K,V> e) {
      LinkedHashMap.Entry<K,V> last;
      //仅当按照LRU原则且e不在最末尾,才执行修改链表,将e移到链表最末尾的操作
      if (accessOrder && (last = tail) != e) {
        //将e赋值临时节点p, b是e的前一个节点, a是e的后一个节点
        LinkedHashMap.Entry<K,V> p =
          (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //设置p的后一个节点为null,因为执行后p在链表末尾,after肯定为null
        p.after = null;
        //p前一个节点不存在,情况一
        if (b == null) // ①
          head = a;
        else
          b.after = a;
        if (a != null) 
          a.before = b;
        //p的后一个节点不存在,情况二
        else // ②
          last = b;
        //情况三
        if (last == null) // ③
          head = p;
        //正常情况,将p设置为尾节点的准备工作,p的前一个节点为原先的last,last的after为p
        else {
          p.before = last;
          last.after = p;
        }
        //将p设置为将p设置为尾节点
        tail = p;
        // 修改计数器+1
        ++modCount;
      }
    }

    5 LinkedHashMap的put()方法

    增加节点:lhm本身并没有实现put 操作,而是通过hm的put函数进行操作,这里有一个非常精彩的设计

    c9f0c4fd71980d8cb0fac433c8647068.png

    截图是hm中put函数的实现,这两个标红函数在hm本身是空回调,而在lhp中,分别进行了实现

    bb4460ad15fdd3b67dc473997a9c80e5.png

    如果该lhp设置访问顺序排序为真的话,那么每次访问的K-V都需要放在双向链表的尾端

    第二个标红的函数 afterNodeInsertion是lhm设计的另一个精彩的地方:

    b445c3067767fd02f113bc05ee788e71.png

    这个函数,做了如下的事:如果给双向链表本身一个节点上限,那么随着数据增长的时候,超过上限后,每次新插入的节点仍然放在尾结点,但是头节点就被干掉了,即维护了一个“最近被插入”的数据结构

    6 LinkedHashMap的remove()

    remove操作与put操作基本一致 也是利用多态性

    8c221abb067be96cae1a8f18798a8c11.png

    4521ed0dbea14f9bfaca25ae4bd92105.png

    这个函数就做了一件事,将该节点冲双向链表中 解耦 ,里面充斥着这样小trick 不用的变量,即时null;

    7 LinkedHashMap的迭代器

    abstract class LinkedHashIterator {
      //记录下一个Entry
      LinkedHashMap.Entry<K,V> next;
      //记录当前的Entry
      LinkedHashMap.Entry<K,V> current;
      //记录是否发生了迭代过程中的修改
      int expectedModCount;
    
      LinkedHashIterator() {
        //初始化的时候把head给next
        next = head;
        expectedModCount = modCount;
        current = null;
      }
    
      public final boolean hasNext() {
        return next != null;
      }
    
      //这里采用的是链表方式的遍历方式,有兴趣的园友可以去上一章看看HashMap的遍历方式
      final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
        if (e == null)
          throw new NoSuchElementException();
        //记录当前的Entry
        current = e;
        //直接拿after给next
        next = e.after;
        return e;
      }
    
      public final void remove() {
        Node<K,V> p = current;
        if (p == null)
          throw new IllegalStateException();
        if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
      }
    }

    LinkedHashMap遍历的方式使链表,顺序访问的话速度应该会更快一些。

    总结

    当我们基于 LinkedHashMap 实现缓存时,通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点,或者根据节点的存活时间判断是否移除该节点等。

    欢迎各位关注我个人的公众号,会不定期更新jdk的源码

    99fdc300b64f08c2456acf81def5ef8e.png
    展开全文
  • 在看LinkedHashMap源码时,可以发现读取操作的get()方法很有意思。 代码如下 public V get(Object key) { Entry&lt;K,V&gt; e = (Entry&lt;K,V&gt;)getEntry(key); if (e == null) return ...

    在看LinkedHashMap源码时,可以发现读取操作的get()方法很有意思。
    代码如下

        public V get(Object key) {
            Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null)
                return null;
            e.recordAccess(this);
            return e.value;
        }

    调用了redordAccess()方法,代码如下:

            void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                if (lm.accessOrder) {
                    lm.modCount++;
                    remove();
                    addBefore(lm.header);
                }
            }

    判断accessOrder为true,就把当前操作的元素放到链表的第一位。

    排序模式accessOrder,属性时布尔,对于访问操作其值为true,插入操作为false。也就是当get(Object key)时,将最新访问的元素放到双向链表的第一位。
    引出了该哈希映射的迭代顺序就是最后访问其条目的顺序,也就很适合构建LRU缓存

    LRU算法 :LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高
    又知道,每次addEntry()后都会调用removeEldestEntry()方法

        void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex);
    
            // Remove eldest entry if instructed
            Entry<K,V> eldest = header.after;
            //调用了默认返回false的removeEldestEntry()
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            }
        }
    
      protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
          //默认返回false
            return false;
        }

    只需要稍作修改就可以构建一个有稳定状态的,每次添加新条目都会淘汰最旧条目的映射。

    展开全文
  • 题目:已知一个 HashMap<Integer,User>集合, User 有 name(String)和 age(int)属性。请写一个方法实现对 HashMap 的排序功能,该方法接收 HashMap<Integer,User>为形参,返回类型为 HashMap&l...

    题目:已知一个 HashMap<Integer,User>集合, User 有 name(String)和 age(int)属性。请写一个方法实现对
    HashMap 的排序功能,该方法接收 HashMap<Integer,User>为形参,返回类型为 HashMap<Integer,User>,
    要求对 HashMap 中的 User 的 age 倒序进行排序。排序时 key=value 键值对不得拆散。

    public class HashMapTest {
        public static void main(String[] args) {
            HashMap<Integer, User> users = new HashMap<Integer, User>();
            users.put(1, new User("张三", 25L));
            users.put(3, new User("李四", 22L));
            users.put(2, new User("王五", 28L));
            System.out.println(users);
            HashMap<Integer, User> sortHashMap = sortHashMap(users);
            System.out.println(sortHashMap);
        }
    
        public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) {
            HashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>();
            Set<Map.Entry<Integer, User>> entrySet = map.entrySet();
            List<Map.Entry<Integer, User>> list = new ArrayList<Map.Entry<Integer, User>>();
            list.addAll(entrySet);
            //根据年龄排倒序
            Collections.sort(list, new Comparator<Map.Entry<Integer, User>>() {
                public int compare(Map.Entry<Integer, User> o1, Map.Entry<Integer, User> o2) {
                    if (o1.getValue().getAge() - o2.getValue().getAge() > 0) {
                        return -1;
                    } else if (o1.getValue().getAge() - o2.getValue().getAge() < 0) {
                        return 1;
                    }
                    return 0;
                }
            });
            for (Map.Entry<Integer, User> entry : list) {
                linkedHashMap.put(entry.getKey(), entry.getValue());
            }
            return linkedHashMap;
        }
    }
    public class User {
        private String username;
        private Long age;
    
        public Long getAge() {
            return age;
        }
    
        public void setAge(Long age) {
            this.age = age;
        }
    
        public String getUsername() {
            return username;
        }
    
        public void setUsername(String username) {
            this.username = username;
        }
    
        public User(String username, Long age) {
            this.username = username;
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "User{" +
                    "username='" + username + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

    转载于:https://my.oschina.net/u/3782515/blog/2050404

    展开全文
  • LinkedHashMap和TreeMap排序实现

    千次阅读 2017-09-25 23:10:46
     Comparator可以对集合对象或者数组进行排序的比较器接口,实现该接口的public compare(T o1,To2)方法即可实现排序,该方法主要是根据第一个参数o1,小于、等于或者大于o2分别返回负整数、0或者正整数。如下: ...

    TreeMap

          TreeMap默认是升序的,如果我们需要改变排序方式,则需要使用比较器:Comparator。

          Comparator可以对集合对象或者数组进行排序的比较器接口,实现该接口的public compare(T o1,To2)方法即可实现排序,该方法主要是根据第一个参数o1,小于、等于或者大于o2分别返回负整数、0或者正整数。如下:

    public class TreeMapTest {
        public static void main(String[] args) {
            Map<String, String> map = new TreeMap<String, String>(
                    new Comparator<String>() {
                        public int compare(String obj1, String obj2) {
                            // 降序排序
                            return obj2.compareTo(obj1);
                        }
                    });
            map.put("c", "ccccc");
            map.put("a", "aaaaa");
            map.put("b", "bbbbb");
            map.put("d", "ddddd");
            
            Set<String> keySet = map.keySet();
            Iterator<String> iter = keySet.iterator();
            while (iter.hasNext()) {
                String key = iter.next();
                System.out.println(key + ":" + map.get(key));
            }
        }
    }

    结果:

     d:ddddd 
     c:ccccc 
     b:bbbbb 
     a:aaaaa

    上面例子是对根据TreeMap的key值来进行排序的,但是有时我们需要根据TreeMap的value来进行排序。对value排序我们就需要借助于Collections的sort(List<T> list, Comparator<? super T> c)方法,该方法根据指定比较器产生的顺序对指定列表进行排序。但是有一个前提条件,那就是所有的元素都必须能够根据所提供的比较器来进行比较。如下:

    public class TreeMapTest {
        public static void main(String[] args) {
            Map<String, String> map = new TreeMap<String, String>();
            map.put("d", "ddddd");
            map.put("b", "bbbbb");
            map.put("a", "aaaaa");
            map.put("c", "ccccc");
            
            //这里将map.entrySet()转换成list
            List<Map.Entry<String,String>> list = new ArrayList<Map.Entry<String,String>>(map.entrySet());
            //然后通过比较器来实现排序
            Collections.sort(list,new Comparator<Map.Entry<String,String>>() {
                //升序排序
                public int compare(Entry<String, String> o1,
                        Entry<String, String> o2) {
                    return o1.getValue().compareTo(o2.getValue());
                }
                
            });
            
            for(Map.Entry<String,String> mapping:list){ 
                   System.out.println(mapping.getKey()+":"+mapping.getValue()); 
              } 
        }
    }

     运行结果

          a:aaaaa 
          b:bbbbb 
          c:ccccc 
          d:ddddd

    HashMap

          我们都是HashMap的值是没有顺序的,他是按照key的HashCode来实现的。对于这个无序的HashMap我们要怎么来实现排序呢?参照TreeMap的value排序,我们一样的也可以实现HashMap的排序。

    public class HashMapTest {
        public static void main(String[] args) {
            Map<String, String> map = new HashMap<String, String>();
            map.put("c", "ccccc");
            map.put("a", "aaaaa");
            map.put("b", "bbbbb");
            map.put("d", "ddddd");
            
            List<Map.Entry<String,String>> list = new ArrayList<Map.Entry<String,String>>(map.entrySet());
            Collections.sort(list,new Comparator<Map.Entry<String,String>>() {
                //升序排序
                public int compare(Entry<String, String> o1,
                        Entry<String, String> o2) {
                    return o1.getValue().compareTo(o2.getValue());
                }
                
            });
            
            for(Map.Entry<String,String> mapping:list){ 
                   System.out.println(mapping.getKey()+":"+mapping.getValue()); 
              } 
         }
    }

    运行结果

          a:aaaaa 
          b:bbbbb 
          c:ccccc 
          d:ddddd

    HashMap通过LinkedHashMap排序

    public class TestMapSortByValue {
    
     
    
        public static void main(String[] args) {
    
            Map<String, Integer> map = new HashMap<String, Integer>();
    
            map.put("d",4);
    
            map.put("a",1);
    
            map.put("c",3);
    
            map.put("e",5);
    
            map.put("b",2);
    
            //排序前
    
            System.out.println("before sort");
    
            for(Map.Entry<String, Integer> entry:map.entrySet()){
    
                System.out.println(entry.getKey()+"->"+entry.getValue());
    
            }
    
            System.out.println();
    
             
    
            //将map转成list
    
            List<Map.Entry<String, Integer>> infos = new ArrayList<Map.Entry<String, Integer>>(map.entrySet());
    
            //对list排序,实现新的比较器
    
            Collections.sort(infos, new Comparator<Map.Entry<String, Integer>>(){
    
                @Override
    
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
    
                    return o1.getValue() - o2.getValue();
    
                }
    
            });
    
            //申明新的有序 map,根据放入的数序排序
    
            Map<String, Integer> lhm = new LinkedHashMap<String, Integer>();
    
            //遍历比较过后的map,将结果放到LinkedHashMap
    
            for(Map.Entry<String, Integer> entry:infos){
    
                lhm.put(entry.getKey(), entry.getValue());
    
            }
    
            //遍历LinkedHashMap,打印值
    
            System.out.println("after sort");
    
            for(Map.Entry<String, Integer> entry:lhm.entrySet()){
    
                System.out.println(entry.getKey()+"->"+entry.getValue());
    
            }
    
        }
    
    }
    结果:
    before sort
    d->4
    e->5
    b->2
    c->3
    a->1
     
    after sort
    a->1
    b->2
    c->3
    d->4
    e->5

















    展开全文
  • 这种方法对于排序存在许多相同元素的情况有些浪费,明显即使值相等,两个元素之间也要比较一下,这在现实中是没有意义的. 典型例子就是学生成绩统计的问题,例如高考中,满分是150,成千上万的学生成绩都在0-150之间,平
  • LinkedHashMap在不同排序方式下的遍历

    千次阅读 2018-09-21 11:05:23
    LinkedHashMap字面上意思为有序集合,有两种排序方式,分别是按输入顺序与读取顺序,可通过以下构造方法来指定其排序方式: public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)...
  • hashMap,treeMap,LinkedHashMap的默认排序

    千次阅读 2017-01-11 13:08:51
     TreeMap:能够把它保存的记录根据键(key)排序,默认是按升序排序,也可以指定排序的比较器,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。...
  • 使用LinkedHashMap进行分数排序

    千次阅读 2009-08-27 12:02:00
    这种方法对于排序存在许多相同元素的情况有些浪费,明显即使值相等,两个元素之间也要比较一下,这在现实中是没有意义的.典型例子就是学生成绩统计的问题,例如高考中,满分是150,成千上万的学生成绩都在0-150之间,平均一...
  • LinkedHashMap

    2016-06-30 10:10:59
    LinkedHashMap实现与HashMap...默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。 可以重写removeEldestEntry方法返回...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 337
精华内容 134
关键字:

linkedhashmap排序方法