综合技术

Android中需要了解的数据结构(三)

微信扫一扫,分享到朋友圈

Android中需要了解的数据结构(三)
0

LinkedHashMap继承HashMap,所有HashMap中一些成员变量、方法LinkedHashMap中都是有的。

LinkedHashMap内部维护了一个双向链表,解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。

LinkedHashMap元素的访问顺序也提供了相关支持,也就是我们常说的 LRU(最近最少使用)原则。

LinkedHashMap 拥有与 HashMap相同的底层哈希表结构,即数组+单链表+红黑树,也拥有相同的扩容机制。

public class LinkedHashMap<K,V>extends HashMap<K,V>
        implements Map<K,V>{
            public LinkedHashMap() {
            // 调用HashMap的构造方法,其实就是初始化Node<K,V>[] table
            super();
            // 这里是指是否基于访问排序,默认为false
            accessOrder = false;
        }
        
         /**
         * 双向链表的头部
         */
        transient LinkedHashMap.Entry<K,V> head;
     
        /**
         * 双向链表的尾部
         */
        transient LinkedHashMap.Entry<K,V> tail;
     
        /**
         * 遍历元素的顺序,如果是true按照访问顺序,如果是false则按照插入顺序
         * @serial
         */
        final boolean accessOrder;
    }
复制代码

基本跟HashMap一致,只是增加了一个accessOrder的属性而已,该属性默认false,即默认按照插入顺序遍历。

/**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
复制代码

静态内部类LinkedHashMapEntry继承HashMap.Node<K,V>存储键值对,用 before 与 next 指针维护插入键值对的顺序。

LinkedHashMap中put方法没有重写,因此和HashMap是一样的,但也有不同,不同在于LinkedHashMap实现了afterNodeAccess,afterNodeInsertion方法
看HashMap put源码

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);      //这个方法HashMap是空实现,这里是发生hash冲突后,找到有相同key对值进行处理时调用
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);     //这个方法HashMap也是空实现,这里是完成新数据put后调用
        return null;
    }
    
复制代码

可以看到每次添加新节点的时候实际上是调用 newNode 方法生成了一个新的节点,但是很明显HashMap中的newNode方法没有操作双向链表节点的关系,所以LinkedHashMap复写的该方法

//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);
            // 将 Entry 接在双向链表的尾部
            linkNodeLast(p);
            return p;
        }

        // newNode 中新节点,放到双向链表的尾部
        private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
            // 添加元素之前双向链表尾部节点
           LinkedHashMap.Entry<K,V> last = tail;
           // tail 指向新添加的节点
           tail = p;
           //如果之前 tail 指向 null 那么集合为空新添加的节点 head = tail = p
           if (last == null)
               head = p;
           else {
               // 否则将新节点的 before 引用指向之前当前链表尾部
               p.before = last;
               // 当前链表尾部节点的 after 指向新节点
               last.after = p;
           }
        }

        //按需删除最早插入的一个元素
        void afterNodeInsertion(boolean evict) { // possibly remove eldest
            LinkedHashMapEntry<K,V> first;
            if (evict && (first = head) != null && removeEldestEntry(first)) {
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
        }
        
        //通过afterNodeAccess方法维护访问顺序,每次访问该元素就将该元素移动到双向链表的末尾
        void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) { //accessOrder用到了,如果是按照访问元素顺序遍历并且当前节点不是尾节点,将该元素移到到最后一个
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<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;
        }
    }
    
复制代码

同样的LinkedHashMap 没有重写的 remove 方法,使用的仍然是 HashMap 中的代 HashMap 中的 remove 方法:

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }   
    
    //LinkedHashMap中实现
        //从链式关系中删除节点e
        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 的 remove 方法将 Hash 表的中节点的删除操作完成,然后通过LinkedHashMap中的afterNodeRemoval来维护链表。

同时发现上述的LinkedHashMap的实现中都会有accessOrder的判断,这个就是用来维护访问顺序。

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

    /**
     * {@inheritDoc}
     */
    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }
复制代码

在我们的get方法中也会去调用 afterNodeAccess(e)
,可以看出当我们使用 accessOrder 为 true 后,我们访问元素会将它移到最后。

LRU

即近期最少使用,在Glide 的三级缓存中内存缓存中使用了这种缓存策略,具体实现LruCache类。

LRU 算法实现当达到设定阈值的时候,这个阈值可能是内存不足,或者容量达到最大,找到最近最少使用的存储元素进行移除,保证新添加的元素能够保存到集合中。

public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        //这里指定了该集合的最大容量,一旦集合容量大于该容量则会调用trimToSize方法来减少容量。
        this.maxSize = maxSize;
        //这里创建了LinkedHashMap并且第三个参数指定为true.该参数为true时LinkedHashMap开启LRU算法。
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }
复制代码

从LruCache的构造函数中可以看到正是用了LinkedHashMap的访问顺序。

public final V put(K key, V value) {
             //不可为空,否则抛出异常
            if (key == null || value == null) {
                throw new NullPointerException("key == null || value == null");
            }
            V previous;
            synchronized (this) {
                //插入的缓存对象值加1
                putCount++;
                //增加已有缓存的大小
                size += safeSizeOf(key, value);
               //向map中加入缓存对象
                previous = map.put(key, value);
                //如果已有缓存对象,则缓存大小恢复到之前
                if (previous != null) {
                    size -= safeSizeOf(key, previous);
                }
            }
            //entryRemoved()是个空方法,可以自行实现
            if (previous != null) {
                entryRemoved(false, key, previous, value);
            }
            //调整缓存大小(关键方法)
            trimToSize(maxSize);
            return previous;
        }
        
        
         public void trimToSize(int maxSize) {
        //死循环
        while (true) {
            K key;
            V value;
            synchronized (this) {
                //如果map为空并且缓存size不等于0或者缓存size小于0,抛出异常
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }
                //如果缓存大小size小于最大缓存,或者map为空,不需要再删除缓存对象,跳出循环
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }
                
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                //删除该对象,并更新缓存大小
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            //移除时会调用的回调函数,本身没有具体实现需要使用时要自己重写
            entryRemoved(true, key, value, null);
        }
    }
复制代码

简单来讲就是每次存放新元素到集合中时间,会根据设定的maxSize来做判断,若果高过的最大的size则会移除近期最少使用的元素。

HashMap、LinkedHashMap、TreeMap有什么区别,应用场景是什么?

  • HashMap:基于HashMap.Node数组加单向链表实现,非线程安全,地址不连续,查询效率比较低,插入和删除效率比较高,是无序的。适合插入和删除操作频繁的场景。
  • LinkedHashMap:是一个维持双向链表,可分为插入顺序和访问顺序两种,如果是访问顺序,那put和get操作已存在的Entry时,都会把Entry移动到双向链表的表尾。
  • TreeMap:基于红黑树实现,非线程安全,可以按照自然顺序或者自定义顺序自动排序,不允许插入null值,查找效率比较高,适合需要排序的场景。

最后讲一下迭代的方式选择:

// for each map.entrySet()
    Map<String, String> map = new HashMap<String, String>();
    for (Entry<String, String> entry : map.entrySet()) {
        entry.getKey();
        entry.getValue();
    }
    
    //显示调用map.entrySet()的集合迭代器
    Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, String> entry = iterator.next();
        entry.getKey();
        entry.getValue();
    }
    // for each map.keySet(),再调用get获取
    Map<String, String> map = new HashMap<String, String>();
    for (String key : map.keySet()) {
        map.get(key);
    }
    
    // for each map.entrySet(),用临时变量保存map.entrySet()
    Set<Entry<String, String>> entrySet = map.entrySet();
    for (Entry<String, String> entry : entrySet) {
        entry.getKey();
        entry.getValue();
    }
复制代码
//keySet
    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }
     
    //entrySet
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }
复制代码

keySet()和entrySet()返回的set的迭代器,从中我们可以看到只是返回值不同而已,父类相同,所以性能相差不多。只是第三种方式多了一步根据key,get得到value的操作而已。
所以需要key以及value的情况下选择和entrySet()。

阅读原文...

微信扫一扫,分享到朋友圈

Android中需要了解的数据结构(三)
0
稀土掘金

陕西市场监督管理局:所有在陕西被4S店收取金融服务费的车主都可退费

上一篇

国产奥迪Q3于上海车展正式宣布上市

下一篇

评论已经被关闭。

插入图片

热门分类

往期推荐

Android中需要了解的数据结构(三)

长按储存图像,分享给朋友