Java集合之LinkedHashMap
三、LinkedHashMap基本结构
关于LinkedHashMap,先提两点:
1、LinkedHashMap可以认为是HashMap+LinkedList(特别重要: 关键的理解点),即它既使用HashMap操作数据结构,又使用LinkedList维护插入元素的先后顺序。
2、LinkedHashMap的基本实现思想就是----多态。可以说,理解多态,再去理解LinkedHashMap原理会事半功倍;反之也是,对于LinkedHashMap原理的学习,也可以促进和加深对于多态的理解。
看到,LinkedHashMap是HashMap的子类,自然LinkedHashMap也就继承了HashMap中所有非private的方法。再看一下LinkedHashMap中本身的方法:
看到LinkedHashMap中并没有什么操作数据结构的方法,也就是说LinkedHashMap操作数据结构(比如put一个数据),和HashMap操作数据的方法完全一样,无非就是细节上有一些的不同罢了。
解释:上述图充分解释了LinkedHashMap可以认为是HashMap+LinkedList的结合体。
解释: 上述图充分解释了LinkedHashMap可以认为是HashMap+LinkedList的结合体。(相当于在hashmap的基础上加入了before,after指针指向插入顺序前后的节点)
下图是直接抽出LinkedHashMap中LinkedList的部分,要知道这抽出的部分可能是跨多个bucket的节点组成的链条
解释: 下图中的new Entry()是构造的头节点,具体可以看下面第2张图
小疑问:既然linkedHashMap重写了HashMap里面的init方法,那为什么还是初始化16个bucket呢?不是已经重写了init方法了吗?
五、LinkedHashMap存储元素
LinkedHashMap并未重写父类HashMap的put方法,而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m) ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现。
继续看LinkedHashMap存储元素,也就是put(“111”,“111”)做了什么,首先当然是调用HashMap的put方法:
第23行又是一个多态,因为LinkedHashMap重写了addEntry方法,因此addEntry调用的是LinkedHashMap重写了的方法:
因为LinkedHashMap由于其本身维护了插入的先后顺序,因此LinkedHashMap可以用来做缓存(解释:这就是LinkedHashMap可以做缓存的原因),第7行~第9行是用来支持FIFO算法的,这里暂时不用去关心它。看一下createEntry方法:
更多详情参考链接:
https://www.cnblogs.com/xiaoxi/p/6170590.html
之所以LinkHashMap能够实现LRU缓存的理由:
get()方法通过key获取value,与HashMap的区别是:当LinkedHashMap按访问顺序排序的时候,会将访问的当前节点移到链表尾部(头结点的前一个节点),也就是说每次访问之后就放到链表尾部,实现最近最久未使用的淘汰机制,淘汰头部(解释:特别重要)