Java基础之LinkedHashMap源码解析
Java集合源码解析系列
LinkedHashMap
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { /** * HashMap.Node的子类 * 增加了前后节点的引用,因此不再是单链表而是双向链表 */ 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); } } /** * 双向链表的头节点和尾节点 * */ transient LinkedHashMap.Entry<K,V> head; transient LinkedHashMap.Entry<K,V> tail; /** * 排序规则的标志 * false表示按节点插入顺序排序 * true表示按节点访问顺序排序 * 默认是false */ final boolean accessOrder; /** *将节点插入链表尾部 */ private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; //如果是插入第一个节点,则头节点和尾节点都指向这个节点 if (last == null) head = p; //已经插入过节点了,就直接插入链表尾部 else { p.before = last; last.after = p; } } /** *将dst节点替换src节点 */ private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) { LinkedHashMap.Entry<K,V> b = dst.before = src.before; LinkedHashMap.Entry<K,V> a = dst.after = src.after; //src是第一个节点 if (b == null) head = dst; else b.after = dst; //src是最后一个节点 if (a == null) tail = dst; else a.before = dst; } /** *初始化LinkedHashMap,这里在调用HashMap的初始化方法之外,还需要将头节点和尾节点初始化 */ void reinitialize() { super.reinitialize(); head = tail = null; } /** * 这里覆写了HashMap的newNode方法 * 生成新的节点并插入到尾部 */ 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); linkNodeLast(p); return p; } /** * 用next节点替换p节点 */ Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; LinkedHashMap.Entry<K,V> t = new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } /** * 红黑树节点的相关方法 */ TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } /** * 覆写HashMap中的afterNodeRemoval方法 * 将节点从链表中删除 */ void afterNodeRemoval(Node<K,V> e) { 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; } /** * 覆写HashMap中的afterNodeInsertion方法 * evict为true并且removeEldestEntry方法也为true的话就会删除近期最少使用的节点 * 所以这里可以看出LinkedHashMap能实现LRU算法 * 由HashMap的源码可知evict默认是true */ void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; //满足条件则删除近期使用最少的节点 removeNode(hash(key), key, null, false, true); } } /** * 覆写HashMap中的afterNodeAccess方法,每当节点被访问时被调用 * 如果accessOrder为true,也就是LinkedHashMap的节点是按照访问顺序排序的,则需要将节点移到链表的末尾 * 这也是LinkedHashMap实现LRU算法的条件之一,即accessOrder要为true */ void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; 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; } } /** * 可以看到默认accessOrder为false,也就是按节点插入顺序排序 */ public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } /** * 这个构造函数可以设置排序规则 * 所以如果要实现LRU算法,也就是要设置accessOrder为true,就要用这个构造函数 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } /** * 判断值是否存在,只需要循环双向链表 * 这里相比HashMap需要2层循环,提升了效率 */ public boolean containsValue(Object value) { for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; } /** * LinkedHashMap的get方法调用的是HashMap的getNode方法 * 注意这里会调用recordAccess方法 */ public V get(Object key) { Node<K,V> e; //如果没找到返回null if ((e = getNode(hash(key), key)) == null) return null; //如果节点是按照访问顺序排序的,那就得去更新下顺序,把刚刚获取的节点放到链表末尾去 if (accessOrder) afterNodeAccess(e); return e.value; } /** * 跟上面的方法一样,只是如果对应的key的节点不存在,会返回一个默认的数据 */ 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; } /** * 这个好理解,清空数据 */ public void clear() { super.clear(); head = tail = null; } /** * 这个方法用于控制是否要删除近期使用最少的节点 * 默认返回是false,所以如果要实现LRU算法,需要覆写该方法,比如节点满了返回true以便删掉使用较少的节点 */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } <!--省略其他方法--> }
LinkedHashMap没有put方法,是怎么插入数据的呢
- 答案就在newNode方法
/** * 这里覆写了HashMap的newNode方法 * 生成新的节点并插入到尾部 */ 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); linkNodeLast(p); return p; } /** * 红黑树节点的相关方法 */ TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; }
- LinkedHashMap实际只是在HashMap的基础上加上了一个双向链表来保存节点插入的顺序,因此很多的逻辑都和HashMap是一样的。比如插入节点时,LinkedHashMap相比HashMap只需要在HashMap的基础上将节点插入双向链表,以及根据排序要求更新节点的顺序就行了
- 对于插入双向链表的功能,LinkedHashMap覆写了HashMap的newNode方法;而对于更新节点的顺序问题,LinkedHashMap覆写了afterNodeAccess方法和afterNodeInsertion方法
总结
- LinkedHashMap继承自HashMap,是HashMap的子类,因此也不是线程安全的
- LinkedHashMap底层存储结构与HashMap一样,不同的是LinkedHashMap增加了一个双向链表的头节点,插入的数据除了插入HashMap,还会插入链表中,因而可以保存插入节点的顺序
- LinkedHashMap的节点在HashMap节点的基础上增加了前后节点的引用
- LinkedHashMap可以插入null
- LinkedHashMap相比HashMap在查找值和删除值时效率要高
- LinkedHashMap还可以设置按插入顺序排序或是按访问顺序排序,默认是按插入顺序排序
- LinkedHashMap没有put方法,而是覆写了afterNodeAccess方法和afterNodeInsertion方法。当插入的数据已经存在时,会调用afterNodeAccess方法看是否需要将数据插入到链表末尾;当插入的数据是新数据时,会通过afterNodeInsertion方法来根据设置删除近期使用最少的节点
- LinkedHashMap可以用来实现LRU算法。首先需要用可以设置accessOrder的构造函数设置accessOrder为true,也就是按照节点访问顺序排序;然后removeEldestEntry方法设置当超过节点数时返回true,也就是删除近期最少使用的数据
以上是基于Java1.8并且只介绍了常用的一些方法的原理,详细的LinkedHashMap源码请查看:LinkedHashMap源码
欢迎关注我的微信公众号,和我一起学习一起成长!
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
区域生长算法 C++实现
在比赛和项目中用opencv用多了,就会发现很多opencv没有实现的算法,其中一些还是十分常用,在教科书上经常出现的。作为一个弱鸡,有的简单的算法能够自己实现(比如本文所要讲的),有的写到一半就打出GG,有的直接就下不了手。。。作为一个非计算机科班的自动化系学生,想要成为一名视觉算法工程师,还是有很长的路要走啊~~ 区域生长 1.算法原理 其实看上图和这个名字就很容易理解,区域生长是根据预先定义的生长准则将像素或子区域组合为更大区域的过程。基本方法是从一组“种子”点开始(原点),将与种子相似的临近像素(在特定范围内的灰度或颜色)添加到种子栈中,不断迭代,生成一大片区域。严谨的数学定义可以查看冈萨雷斯的数字图像处理。 2.算法实现 算法的步骤如下: 创建一个与原图像大小相同的空白图像 将种子点存入vector中,vector中存储待生长的种子点 依次弹出种子点并判断种子点如周围8领域的关系(生长规则)并与最大与最小阈值进行比较,符合条件则作为下次生长的种子点 vector中不存在种子点后就停止生长 我这里因为项目需要,对原本的区域生长算法多加了最大与最小值的限制,作为默认参数可以不填。...
- 下一篇
第六章 接口,lamda表达式与内部类
接口 接口可以包含常量, 且不需要publish static final修饰, 接口的域会自动添加该修饰符. Java建议不要写多余的代码,因此省略修饰符更简洁. 全部都是常量的接口背离了接口的初衷,不建议使用 Java SE8 中, 允许接口增加静态方法,但这也有悖接口的初衷 接口的默认方法实现用 defalut 修饰, 适用于子类只需要实现其中几个方法的情况, 而其他方法以默认方法形势存在, 子类没必要实现他们. 接口方法命名的二义性需要子类中解决,可以使用InterfaceName.super.Method()解决 接口和类方法的二义性以类的方法优先, 这样可以保证与之前版本的兼容性 不要让一个接口默认方法重新定义Object中的方法, 原因即上一点提到的, 类的方法优先导致默认方法失效. lamda表达式 对于只有一个抽象方法的接口(没有default修饰)),需要这种接口的对象时,就可以提供一个 lambda 表达式。这种接口称为函数式接口(functional interface)。 @FunctionalInterface 注解表明接口是一个函数式接口,这个注解并非必须...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS关闭SELinux安全模块
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2全家桶,快速入门学习开发网站教程
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS8编译安装MySQL8.0.19