源码的魅力 - LinkedHashMap 的工作原理

LinkedHashMap 的工作原理(Android 7.1源码)

简介

LinkedHashMap继承于HashMap,前面文章中我们解析了HashMap的原理(需要的可以打开历史文章进行查看),由于HashMap中的Entry数组是无序的,但是在一些情况下我们需要保存数据的插入顺序或者访问顺序,所以LinkedHashMap就诞生了。

怎样保存插入的顺序呢

    private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        LinkedHashMapEntry<K,V> before, after;
        ...
    }

在前面的HashMap篇中我们讲过HashMapEntry,在LinkedHashMap中就对于这个HashMapEntry再封装了一下,添加了before、after两个指针,这两个指针就是用于保存插入顺序的。

插入顺序如何保存的呢

    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> old = table[bucketIndex];
        LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

在前面的HashMap篇中我们讲过插入数据中会调用CreateEntry,LinkedHashMap重写了这一方法,增加了一步addBefore()方法,方法简单不再赘述,总之就是将每一个entry通过head与after连在一起。

怎么按照指定的顺序遍历呢

    LinkedHashMap<String, String> map = new LinkedHashMap();
    Set<Map.Entry<String, String>> set = map.entrySet();
    Iterator<Map.Entry<String, String>> iterator = set.iterator();
    while (iterator.hasNext()) {
          Map.Entry<String, String> entry = iterator.next();
    } 

通过使用entrySet方法来获取Entry的Set集合再通过Iterator来进行遍历。

entrySet方法的内部实现

    //上面的map.entrySet()方法最终会调用LinkedHashMap的newEntryIterator方法
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new     EntryIterator(); }
    //而EntryIterator 又继承自LinkedHashIterator,然后通过nextEntry来调用
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return nextEntry(); }
    }
    //LinkedHashIterator内部nextEntry方法也是通过after指针一步一步访问
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        LinkedHashMapEntry<K,V> nextEntry    = header.after;
        LinkedHashMapEntry<K,V> lastReturned = null;

        ...

        public boolean hasNext() {
            return nextEntry != header;
        }
        ...

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }

map.entrySet()方法最终会调用LinkedHashMap的newEntryIterator方法,然后再调用EntryIterator的next方法,内部是调用父类的LinkedHashIterator的nextEntry方法,然后通过header的指向的双向链表after一步一步遍历。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 4,295评论 0 16
  • 接口/抽象类意义规范、扩展、回调为其子类提供一个公共的类型 封装子类中得重复内容 定义抽象方法,子类虽然有不同的实...
    MigrationUK阅读 2,212评论 1 28
  • 本篇文章带你从Java源码深入解析关于Java容器的概念。 参考文献: Java容器相关知识全面总结 Java官方...
    Tsy远阅读 20,102评论 13 142
  • 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash 算...
    曹振华阅读 2,531评论 1 37
  • 星星住在银河里 云朵住在空气里 地球住在宇宙里 他们都有大房子 儿子羡慕地问 爸爸 我们的房子在哪里?
    向日葵爱呀爱太阳阅读 206评论 0 0