精华内容
下载资源
问答
  • HashMapLinkedHashMap区别 (非原创) HashMap,LinkedHashMap,TreeMap都属于Map Map 主要用于存储键(key)值(value)对,根据键得到值,因此键不允许键重复,但允许值重复。 HashMap  是一个最常用的Map...

    HashMap和LinkedHashMap的区别(非原创)

    HashMap,LinkedHashMap,TreeMap都属于Map

    Map 主要用于存储键(key)值(value)对,根据键得到值,因此键不允许键重复,但允许值重复。

    HashMap 
    是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值,具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步,可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。

                                                                                        
    LinkedHashMap
    LinkedHashMap也是一个HashMap,但是内部维持了一个双向链表,可以保持顺序

     

    TreeMap 可以用于排序

     

    HashMap的例子
    public static void main(String[] args) {  

          Map<String, String> map = new HashMap<String, String>(); 

          map.put("a3", "aa");

          map.put("a2", "bb"); 

          map.put("b1", "cc");

          for (Iterator iterator = map.values().iterator(); iterator.hasNext();)     {

                String name = (String) iterator.next(); 

                System.out.println(name);   

         }  

      }

     

    输出:bbccaa

    LinkedHashMap例子:

       

    public static void main(String[] args) {   

         Map<String, String> map = new LinkedHashMap<String, String>();

         map.put("a3", "aa");       

         map.put("a2", "bb"); 

         map.put("b1", "cc"); 

         for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {           

                 String name = (String) iterator.next(); 

                 System.out.println(name);     

         }

    }


    输出:
    aa
    bb
    cc

     

    总结归纳为:linkedMap在于存储数据你想保持进入的顺序与被取出的顺序一致的话,优先考虑LinkedMap,hashMap键只能允许为一条为空,value可以允许为多条为空,键唯一,但值可以多个。

    经本人测试linkedMap键和值都不可以为空

    转载于:https://my.oschina.net/u/3717819/blog/1927122

    展开全文
  • 关于HashMap与LinkedHashMap区别 1、HashMap<String,String> hashmap = new HashMap<>(); 当在Map类的集合中使用HashMap时,输入的内容顺序是变化的,每一次运行都是不一样的。 2、LinkedHashMap<...

    关于HashMap与LinkedHashMap的区别

    1、HashMap<String,String> hashmap = new HashMap<>();

    当在Map类的集合中使用HashMap时,输入的内容顺序是变化的,每一次运行都是不一样的。

    2、LinkedHashMap<String,String> linkedhashmap = new LinkedHashMap<>();

    当在Map类的集合中使用LinkedHashMap时,输入的内容顺序是不变的,每一次运行都是一样的。

    3、在使用Map集合时运用putAll可以实现快速的将集合1里的元素copy到集合2里去。

    HashMap<String,String> hashmap1 = new HashMap<>();

    hashmap1.put(“字符串”,“字符串”);

    hashmap1.put(“字符串”,“字符串”);

    hashmap1.put(“字符串”,“字符串”);

    HashMap<String,String> hashmap2 = new HashMap<>();

    hashmap2.putAll(hashmap1);

    public static void main(String[] args) {
        /*
        LinkedHashMap是按顺序植入的,先输入的先输出。
         */
        LinkedHashMap<String, String> map = new LinkedHashMap<>();
        map.put("春眠不觉晓", "第一句");
        map.put("处处闻啼鸟", "第二句");
        map.put("夜来风雨声", "第三句");
        map.put("花落知多少", "第四句");
        LinkedHashMap<String, String> map1 = new LinkedHashMap<>();
        map1.putAll(map);
        System.out.println(map);
        System.out.println(map1);
        System.out.println("============================================================================");
        /*
        HashMap输出的结果是乱序的,每次输出的顺序都不一样。
         */
        HashMap<String, String> map2 = new HashMap<>();
        map2.put("春眠不觉晓", "第一句");
        map2.put("处处闻啼鸟", "第二句");
        map2.put("夜来风雨声", "第三句");
        map2.put("花落知多少", "第四句");
        HashMap<String, String> map3 = new HashMap<>();
        map3.putAll(map2);
        System.out.println(map2);
        System.out.println(map3);
      }
    
    展开全文
  • #HashMap与LinkedHashMap区别 ##LinkedHashMap类代码 public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> 从类的声明来看Link...

    #HashMap与LinkedHashMap的区别 ##LinkedHashMap类代码 public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> 从类的声明来看LinkedHashMap继承自HashMap。那么两者有什么区别呢?

    • linkedHashMap是有序的。

    • private transient Entry<K,V> header; 这个是整个链表的头。

      void init() { header = new Entry<>(-1, null, null, null); header.before = header.after = header; } 在初始化时候对双向链表进行维护。

      //这个entity就是每个key-value对应的实体类, 因为继承自HashMap.Entity,所以自带HashMap.Entity的next,get等属性 private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
      
        //删除当前节点, 将当前链表的收尾重新拼接
        private void remove() {
            before.after = after;
            after.before = before;
        }
      
        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
      
        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
      
        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
      

      } 在HashMap.Entity的基础上添加before和after,构成一个双向链表。

    • 构造函数不同, 添加了accessOrder 用户选择排序的方式

    •   accessOrder     the ordering mode - <tt>true</tt> for
      	access-order, <tt>false</tt> for insertion-order
      

    在构造方法中如果设置为true的话, 那么就按照访问的顺序排序(LRU)否则按照插入顺序排序。

    ##hashMap添加元素代码

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
    
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
    
        createEntry(hash, key, value, bucketIndex);
    }
    
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    

    ##LinkedhashMap添加元素代码 因为LinkedHashMap extends HashMap 所以LinkedHashMap拥有HashMap所有方法。LinkedHashMap集合在添加方法时,默认调用父元素的方法, 并维护双向链表。LinkedHashMap 重写了 addEntry和 createEntry。 addEntry 添加了移除最旧使用的条目。 在LRU中用到 createEntry 在原来的方法上添加了对链表的维护

    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;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }
    
    /**
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }
    

    转载于:https://my.oschina.net/xbding/blog/700108

    展开全文
  • HashMap与LinkedHashMap

    2017-11-19 12:42:28
    HashMap与LinkedHashMap 简介 二者的区别 源码阅读 Best PracticesHashMap与LinkedHashMap1. 简介在日常开发中我们经常会批量操作数据,因此很多高级语言除了提供数组,还给我们提供很多高级的、抽象的数据类型来让...

    HashMap与LinkedHashMap

    1. 简介

    在日常开发中我们经常会批量操作数据,因此很多高级语言除了提供数组,还给我们提供很多高级的、抽象的数据类型来让我们处理批量数据时得心应手。由于这些轮子对于程序的性能是比较关键的轮子,因此很多语言都内置的提供了比较精致的实现。在java中,这种实现被称为集合框架。集合框架包含的接口、类十分丰富,而且功能强大,因此理解并熟悉java集合框架,对于写出正确高效的程序是十分有必要的。java集合框架中包含两个重要的类LinkedHashMapHashMap,它们常常被用于按key-value存储、操作数据,对于常见的操作都是常数的时间复杂度,因此被广泛使用,虽然这两个类的作用类似,但是他们的实现和使用场景稍微不同。

    2. 二者的区别

    HashMapLinkedHashMap都实现了Map接口,二者的存储形式都是采用bucket加链表的形式来进行存储的。二者的主要区别:

    • HashMap由于是按照keyhash值映射到对应的bucket中,无法保证遍历HashMap时的顺序是预期的顺序
    • LinkedHashMapHashMap的基础上加以改进,却可以保证遍历的顺序要么是插入item的顺序或者LRU访问的顺序

    这是因为LinkedHashMap维护了一个双向链表来记录数据插入的顺序,因此在迭代遍历生成的迭代器的时候,是按照双向链表的路径进行遍历的。

    如果选择LRU访问的顺序,LinkedHashMap对于访问过的item会将其移动到双链表的末尾,这样保证最近访问过的item是处于链表末端,因此较老其不经常使用的item会处于链表前端。这个特性恰好符合LRU的思想,因此LinkedHashMap可以用来实现LRU CacheAndroid提供的SDKLruCache类便是利用LinkedHashMap实现了基于Lru规则的缓存功能。

    另外可以发现在java8HashMapLinkedHashMap有了改动,据说在某些Hash碰撞严重时,性能也不会太差。java8之前的Map实现的问题是当出现某个bucket的后面的链表太长了,也就是说发生hash冲突的item太多了,这样会导致访问操作退化到了O(n)

    java8的改进便是当bucket的链表长度大于阈值的时候,会将链表重新组织为一颗红黑树,这样在hash碰撞严重的时候性能还是可以保证到log(n).改进前后的示意图如下所示:

    这里写图片描述

    这里写图片描述

    在使用LinkedHashMapHashMap的时候应该注意Keyhash值是怎么取得,如果不同的key经常出现相同的hash值,则会频繁出现冲突,降低性能。

    同时,由于改进后的HashMap会在某个bucket后的链表长度超过某个阈值时,重新将连边组织为一颗红黑树,因此在java8上的key最好实现Comparable接口来保证key是可以通过compareTo进行比较的,因为这样会简化建立红黑树的判断流程,提高效率。当然如果不实现Comparable接口的话,也会有相应的方法保证hash值冲突的item形成一颗平衡的红黑树。

    3. 源码阅读

    此处选取几个关键的地方进行源码分析:

    1. 对于HashMap重点关注这几个方法
    final void treeifyBin(Node<K,V>[] tab, int hash)
    public V put(K key, V value)
    final void treeify(Node<K,V>[] tab)
    static int tieBreakOrder(Object a, Object b)
    
    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
    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;
    //通过hash找到对应的桶,如果桶空则直接新建一个链表节点置于桶中并成为链表头
    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))))//运气好的话,在链表头就找到了,注意此处key的匹配规则,首先是 == 匹配,然后再是调用equals方法匹配
            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) {//如果查找到了链表尾,认为匹配到key,则新建一个节点
                    p.next = newNode(hash, key, value, null);
                    //java8改进的地方!!!!如果桶内链表的长度大于了阈值则树形化该链表
                    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))))//匹配到一个存在的item
                    break;
                p = e;
            }
        }
        //如果成功匹配了key,则此次put操作仅仅是修改value而没有插入新的节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);//访问元素e的回调,注意比较LinkedHashMap在此处的实现。
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//如果真个hashmap的长度超过了阈值,就说明可能会出现严重的hash冲突此时就应该resize(),rehash。
        resize();
    afterNodeInsertion(evict);//插入元素e的回调,注意比较LinkedHashMap在此处的实现。
    return null;
    }
    
    
    /**
    * Replaces all linked nodes in bin at index for given hash unless
    * table is too small, in which case resizes instead.
    */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果Hash表的桶数小于可以树形化的阈值,则只是扩大桶数,进行再Hash
    //我估计在设计的时候权衡了重建一颗红黑树和再Hash的cost,当桶的数量很少的时候,再hash划算一些
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            //从链表头hd,将每一个节点转化为一个树节点且继续保持链表的顺序
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);//最终树形化链表在这里完成
    }
    }
    
    
    /**
     * Forms tree of the nodes linked from this node.
     * @return root of tree
     */
    final void treeify(Node<K,V>[] tab) {
        TreeNode<K,V> root = null;
        //以当前对象作为root,开始构建一颗红黑树
        for (TreeNode<K,V> x = this, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            if (root == null) {
                x.parent = null;
                x.red = false;
                root = x;
            }
            else {
                K k = x.key;//当前树节点x包含的key
                int h = x.hash;//当前树节x点的hash值
                Class<?> kc = null;//x节点包含的key的类
                //从红黑树的根节点开始寻找合适的插入的位置,然后再平衡该树。
                for (TreeNode<K,V> p = root;;) {
                    int dir, ph;
                    K pk = p.key;
                    //正常来讲,由于HashMap是树形化一个桶内的链表,因此
                    //每个链表的节点的hashCode()返回的值应该是一样的。
                    //因此这里两个分支(ph = p.hash) > h 和 ph < h应该都不会被执行
                    //这里会直接进入分支3进行判断
                    if ((ph = p.hash) > h)//分支1
                        dir = -1;
                    else if (ph < h)//分支2
                        dir = 1;
                       //分支3 当两个节点的hash值相等的时候(事实上绝大部分都是这样的情况)
                        //则反射判断x节点的key的类是否是实现了Comparable接口,如果实现了则利用compareTo方法进行比较判断,从而决定插入的位置;
                        //如果没有实现Comparable接口或者实现了Comparable接口但是compareTo比较的结果还是一致,则利用tieBreakOrder来决定大小。
                        //因为红黑树的节点都要有大小区分的,不能出现大小相同的节点,因此无论采用哪种量化方式,一定得比较个大小出来。
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);//当俩节点hashCode返回值相等且没有实现comparable接口,在这种尴尬僵持的局面,就需要调用tieBreakOrder方法
                    //来一较高低了。因此java8中对于HashMap的文档中建议Key要实现Comparable接口,这样此处就不会进入到如此尴尬僵持的局面,会提高些许性能,毕竟后面
                    //打破僵局是需要付出代价的
    
                    TreeNode<K,V> xp = p;
                    //直到走到叶节点,则进行插入
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;//如果该节点x比父亲节点p小,则作为节点p的左孩子
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);//红黑树都有的操作,插入节点后需要进行调整以继续保证红黑树的性质
                        break;
                    }
                }
            }
        }
        moveRootToFront(tab, root);//保证桶内存放的是红黑树的根节点root
    }
    
    /**
     * Forms tree of the nodes linked from this node.
     * @return root of tree
     */
    final void treeify(Node<K,V>[] tab) {
        TreeNode<K,V> root = null;
        //以当前对象作为root,开始构建一颗红黑树
        for (TreeNode<K,V> x = this, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            if (root == null) {
                x.parent = null;
                x.red = false;
                root = x;
            }
            else {
                K k = x.key;//当前树节点x包含的key
                int h = x.hash;//当前树节x点的hash值
                Class<?> kc = null;//x节点包含的key的类
                //从红黑树的根节点开始寻找合适的插入的位置,然后再平衡该树。
                for (TreeNode<K,V> p = root;;) {
                    int dir, ph;
                    K pk = p.key;
                    //正常来讲,由于HashMap是树形化一个桶内的链表,因此
                    //每个链表的节点的hashCode()返回的值应该是一样的。
                    //因此这里两个分支(ph = p.hash) > h 和 ph < h应该都不会被执行
                    //这里会直接进入分支3进行判断
                    if ((ph = p.hash) > h)//分支1
                        dir = -1;
                    else if (ph < h)//分支2
                        dir = 1;
                       //分支3 当两个节点的hash值相等的时候(事实上绝大部分都是这样的情况)
                        //则反射判断x节点的key的类是否是实现了Comparable接口,如果实现了则利用compareTo方法进行比较判断,从而决定插入的位置;
                        //如果没有实现Comparable接口或者实现了Comparable接口但是compareTo比较的结果还是一致,则利用tieBreakOrder来决定大小。
                        //因为红黑树的节点都要有大小区分的,不能出现大小相同的节点,因此无论采用哪种量化方式,一定得比较个大小出来。
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);//当俩节点hashCode返回值相等且没有实现comparable接口,在这种尴尬僵持的局面,就需要调用tieBreakOrder方法
                    //来一较高低了。因此java8中对于HashMap的文档中建议Key要实现Comparable接口,这样此处就不会进入到如此尴尬僵持的局面,会提高些许性能,毕竟后面
                    //打破僵局是需要付出代价的
    
                    TreeNode<K,V> xp = p;
                    //直到走到叶节点,则进行插入
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;//如果该节点x比父亲节点p小,则作为节点p的左孩子
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);//红黑树都有的操作,插入节点后需要进行调整以继续保证红黑树的性质
                        break;
                    }
                }
            }
        }
        moveRootToFront(tab, root);//保证桶内存放的是红黑树的根节点root
    }
    
    
    
    /**
     * Tie-breaking utility for ordering insertions when equal
     * hashCodes and non-comparable. We don't require a total
     * order, just a consistent insertion rule to maintain
     * equivalence across rebalancings. Tie-breaking further than
     * necessary simplifies testing a bit.
     */
    static int tieBreakOrder(Object a, Object b) {
        int d;
        if (a == null || b == null ||
            (d = a.getClass().getName().
             compareTo(b.getClass().getName())) == 0)//先利用两对象的类名的大小比较,若仍然陷入僵局,则调用
            //System.identityHashCode()的方法该方法会返回对象唯一的真实的hash值无论对象的类是否重写了hashCode方法
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                 -1 : 1);
        return d;
    }
    

    以上部分简要的分析了HashMap的改进处的源码。

    1. 对于LinkedHashMap,主要阅读分析其如何保证迭代的顺序具有LRU的性质
      LinkedHashMapHashMap的子类,只是稍加改造便使得其具有链表的顺序性质。
    
    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
    
    
    /**
    * 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;//维护的双向链表的表尾
    
    /**
    * The iteration ordering method for this linked hash map: <tt>true</tt>
    * for access-order, <tt>false</tt> for insertion-order.
    *
    * @serial
    */
    final boolean accessOrder;//是访问顺序还是插入顺序

    主要关注以下几个方法:

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) 
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p)
    
    
    void afterNodeAccess(Node<K,V> e)
    
    
    void afterNodeInsertion(boolean evict)
    
    
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
    
    //这个方法是HashMap的hook方法,只是简单的扩展了HashMap的Node类,就完成了LinkedHashMap的大部分功能
    //不得不说类的设计很巧妙
    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);//将节点e
    linkNodeLast(p);//将该Entry链接到LinkedHashMap维护的双向链表的表尾
    return p;
    }
    /**
    * HashMap.Node subclass for normal LinkedHashMap entries.
    */
    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);
    }
    }
    
    // link at the end of list
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;//tail是维护的双链表的表尾
    tail = p;
    //接下就是简单的链表链接操作
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
    }

    由于LinkedHashMap没有重写put方法,因此它复用了HashMapput方法,只是简单重写了hook方法newNode。因此put方法不用分析了。到此应该就可以去看迭代器的实现了,讲道理的话应该是按照双向链表的顺序来迭代的。

    
    abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    
    LinkedHashIterator() {
        next = head;//head存放的是双向链表的表头
        expectedModCount = modCount;
        current = null;
    }
    
    public final boolean hasNext() {
        return next != null;
    }
    
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;//依次迭代
        return e;
    }
    }
    

    自此已经大致清楚了LinkedHashMap是如何简单的改造了HashMap而拥有了顺序的迭代。

    LinkedHashMap不仅仅遍历是有序的,而且还可以选择是何种顺序,是插入顺序还是访问顺序

    acceeOrder的定义了遍历是何种顺序,该值默认是false,若想为true,需要显示的指定。

    
    void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //如果是访问顺序,则将节点e放在链表尾部
    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还是get操作都会导致该元素e会被放在链表尾部。这样链表表头部分的元素的访问时间就相对久远了,这个特性就恰恰比较符合LRU的思想。因此当LinkiedHashMap的元素个数超过一定的阈值时(因为缓存的容量是有限的),就需要删除某些缓存item了。在LinkedHashMap中就有这样的CallBack来完成这个目的。

    
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //如果该LinkedHashMap允许删除老元素,则移除老元素
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
    }
    

    LinkedHashMap默认是不移除老元素,因此要实现Lru需要重写该方法。

    
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return false;
    }
    
    

    通常会这么重写

    private static final int MAX_ENTRIES = 100;
    
    protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > MAX_ENTRIES;
    }
    

    可以看出来LinkedHashMap只是稍微加以改进,就具备了额外的功能。这种类的设计十分精致,值得借鉴。
    HashMap预留了几个关键的hook方法给扩展类(此处是LinkedHashMap),例如newNode(),afterAccess() afterInsertion()等。这样就是策略和机制分离了,便于扩展类添加更丰富的功能。当然我们也可以按照需要扩展HashMap,从而改变其某些行为。

    但是HashMap类中的TreeNode怎么会去继承子类LinkedHashMapEntry,难道仅仅是为了少些几行代码?我觉得这个设计不是很好。毕竟父类不应该去获取子类的某些信息,有点本末倒置。

    /**
    * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
    * extends Node) so can be used as extension of either regular or
    * linked node.
    */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    

    4. Best Practices

    • 在使用HashMap时应该尽量保证keyhashCode返回值分布均匀性;在java8上使用时key应该尽量实现comparable接口。

      • LinkedHashMapHashMap性能的比较:在基本的put get remove操作,两者的性能几乎相近,由于LinkedHashMap维护着一个双向链表,因此性能可能稍微差一点点。但是在迭代遍历的时候,因为LinkedHashMap遍历的所有的插入的元素,而HashMap是遍历的整个HashMap(包括一些空桶),因此LinkedHashMap的性能稍微优于HashMap

      • LinkedHashMap可以保持任意的Map的顺序信息,就像这样使用:

      
      void foo(Map m) {
           Map copy = new LinkedHashMap(m);
           ...
      }
    展开全文
  • HashMapLinkedHashMap区别 LinkedHashMap是继承于HashMap,是基于HashMap和双向链表来实现的。 HashMap无序;LinkedHashMap有序,可分为插入顺序和访问顺序两种。如果是访问顺序,那put和get操作已存在的Entry...
  • Java HashMap与LinkedHashMap区别

    千次阅读 2015-02-05 15:35:18
    HashMap与LinkedHashMap是Map接口的两个实现类,它们最大的区别就是HashMap的元素是无序存放的,LinkedHashMap的元素是有序存放的,示例: Map hashMap = new HashMap(); Map linkedHashMap = new LinkedHashMap(); ...
  • HashMapLinkedHashMap属于线程不安全的 HashTable属于线程安全 再来看看HashMapLinkedHashMap的结构图,是不是秒懂了。LinkedHashMap其实就是可以看成HashMap的基础上,多了一个双向链表来维持顺序。 ...
  • LinkedHashMap常作为HashMap(了解HashMap)的替补出现,它继承自HashMap,并继承了HashMap百分之八十的功能,剩下的百分之二十的功能则是用于排序。 1,LinkedHashMap同样使用table存储元素,但元素不再是Node类...
  • LinkedHashMap TreeMap Map主要用于存储健值对,根据键得到值,因此不允许键重复(重复了覆盖了),但允许值重复。 Hashmap 是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值,具有很快的...
  • 此处,我们好好谈谈HashMap 主要关注几个点: 初始化大小是16,如果事先知道数据量的大小,建议修改默认初始化大小。 减少扩容次数,提高性能 ,这是我一直会强调的点 最大的装载因子默认是0.75,当HashMap中元素个...
  • 数据结构算法-HashMap与LinkedHashMap

    千次阅读 2018-04-08 14:37:02
    数据结构算法-HashMap与LinkedHashMap Map 基本概念 Map 一般在开发中使用非常广泛,常用的有HashMapLinkedHashMap,TreeMap等等,由于使用的时候一般是有key和value一一对应,所以称之为Map。 百度...
  • HashMapLinkedHashMap区别 HashMap,LinkedHashMap,TreeMap都属于Map Map 主要用于存储键(key)值(value)对,根据键得到值,因此键不允许键重复,但允许值重复。 HashMap 是一个最常用的Map,它根据键的HashCo...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 58,708
精华内容 23,483
关键字:

hashmap与linkedhashmap区别