一,简介
jdk中HashMap和HashSet的遍历是无序的,而LinkedHashMap和LinkedHashSet是两种可以预知迭代顺序的集合类。LinkedHashMap支持两种迭代顺序(插入顺序和访问顺序,其中默认是插入顺序)。而LinkedHashSet仅支持按插入顺序遍历。
二,实现原理
LinkedHashMap<K,V>继承自HashMap<K,V>,与HashMap的区别是LinkedHashMap底层还维护着一个双向循环链表(用于记录元素的插入顺序或访问顺序)。
结构图:
JDK源码:
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { private static final long serialVersionUID = 3801124242820219131L; /** * The head of the doubly linked list. */ private transient Entry<K,V> header;//双向循环链表的表头 /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * * @serial */ private final boolean accessOrder; public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false;//默认为插入顺序,如果要以访问顺序遍历,需要设置为true } public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } /** *LinkedHashMap重写了HashMap中的get方法 */ public V get(Object key) { Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; e.recordAccess(this);//记录访问顺序 return e.value; } /** * LinkedHashMap entry. * 由于继承于HashMap.Entry<K,V>,所以Entry<K,V>实际上包含以下三个Entry<K,V>属性:before,after,next(HashMap是基于单链表+数组实现的,next单链表节点的后继元素)。 */ 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); } /** * Removes this entry from the linked list. */ 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) {//如果是访问顺序,则修改header引用为最新访问的节点元素 lm.modCount++; remove(); addBefore(lm.header); } } void recordRemoval(HashMap<K,V> m) { remove(); } } }
LinkedHashMap中的访问顺序遍历,已经为我们实现LRU算法(最近最少使用算法)提供了便利。记录访问顺序:将最新访问的元素添加到双向循环链表的表头,并从原来的位置删除。由于链表的增加、删除操作是常量级的,故并不会带来性能的损失。LinkedHashMap类是重写了HashMap中的get方法(添加记录访问顺序逻辑)。
下面介绍一下LinkedHashSet的实现原理
LinkedHashSet是继承HashSet实现的,而HashSet是不具备按插入顺序遍历的。那么LinkedHashSet又是如何实现按插入顺序遍历的呢?JDK源码如下:
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; /** * Constructs a new, empty linked hash set with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity of the linked hash set * @param loadFactor the load factor of the linked hash set * @throws IllegalArgumentException if the initial capacity is less * than zero, or if the load factor is nonpositive */ public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } /** * Constructs a new, empty linked hash set with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity of the LinkedHashSet * @throws IllegalArgumentException if the initial capacity is less * than zero */ public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } /** * Constructs a new, empty linked hash set with the default initial * capacity (16) and load factor (0.75). */ public LinkedHashSet() { super(16, .75f, true); } /** * Constructs a new linked hash set with the same elements as the * specified collection. The linked hash set is created with an initial * capacity sufficient to hold the elements in the specified collection * and the default load factor (0.75). * * @param c the collection whose elements are to be placed into * this set * @throws NullPointerException if the specified collection is null */ public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } }
通过阅读JDK源码,发现LinkedHashSet中并没有像LinkedHashMap一样实现一个记录可预订顺序的双向循环链表。那肯定是HashSet帮LinkedHashSet做了这件事, 于是乎继续阅读HashSet实现源码。
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<E,Object>(); } /**访问权限为public,组合的是HashMap*/ public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<E,Object>(initialCapacity, loadFactor); } /**访问权限为defalut为包内访问,组合的是LinkedHashMap,由于HashSet没有提供可以设置 * accessOrder属性的构造函数,则LinkedHashSet仅具备按插入顺序遍历的功能 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor); } }
通过阅读HashSet的源码,LinkedHashSet最终是组合LinkedHashMap来实现的,但由于父类HashSet没有提供赋值accessOrder属性的入口,所以只具备按插入顺序遍历的功能。平常我们在应用中使用的HashSet都是基于组合HashMap实现的,所以HashSet的遍历是无序的。
三,总结
LinkedHashMap(插入顺序和访问顺序)和LinkedHashSet(插入顺序),这两种集合类操作是非线程安全的。
相关推荐
RiteLinked-类似HashMap的容器,以用户可控制的顺序保存其键值对 提供了LinkedHashMap和LinkedHashSet更多最新版本。 您可以在std或no_std环境中轻松使用它。 一些实用的功能组合,支持,帮助您更好地将其嵌入到...
RiteLinked——类似HashMap的容器,以用户可控的顺序保存它们的键值对RiteLinked提供了LinkedHashMap和LinkedHashSet更多最新版本。您可以在std或no_std环境中轻松使用它。一些实用的功能组合,支持,帮助您更好地将...
此板条箱是链接哈希表的一个分支,用于构建o hashlink-类HashMap的容器,将其键值对保存在用户中可控制的顺序该板条箱是基于hash-brown的links-hash-map的一个分叉,用于实现LinkedHashMap,LinkedHashSet和LruCache...
linked_hash_set此库基于元素的插入顺序提供了具有可预测迭代顺序的哈希集。 它实现为linked_hash_set。此库基于元素的插入顺序提供了具有可预测迭代顺序的哈希集。 它实现为linked_hash_map :: LinkedHashMap,其中...
Java的集合类总结,包括HashMap、HashSet、HashTable、LinkedHashMap、LinkedHashSet、ArrayList、LinkedList、ConcurrentHashMap的实现原理,很详实,面试的话可以认真看看
// HashSet不保证迭代顺序, LinkedHashSet按照元素插入的顺序迭代. // 学习List对象容器的使用 // List容器中的对象允许重复 // 常用的list接口的实现类有ArrayList和LinkedList // 学习map对象容器的使用 // map...
LinkedHashMap源代码,Java中Map的一种实现子类。
这是关于Java学习的主要针对LinkedHashMap的实现原理
HashMap,HashTable,LinkedHashMap,TreeMap的区别
这个demo主要讲解了LinkedHashmap的使用,希望可以帮助需要的同学.
java中HashMap,LinkedHashMap,TreeMap,HashTable的区别
深入Java集合学习系列(四): LinkedHashMap的实现原理
主要介绍了 java HashMap,TreeMap与LinkedHashMap的详解的相关资料,这里提供实例代码,帮助大家学习理解 这部分的内容,需要的朋友可以参考下
LinkedHashMap是Java中的一种特殊类型的HashMap,它保留了插入顺序,即按照元素插入的先后顺序进行排序
如果要在迭代时保证插入顺序,请使用LinkedHashMap 。 这些键是真正键入的且唯一的,这意味着1!==“ 1”。 明智地选择您的地图。 选择集合时,值得理解您要解决的问题。 少量条目的本将显着提高速度。 但是,...
可以按照元素的插入顺序进行访问,也可以按照元素的访问顺序进行访问。要注意一点的是LinkedHashMap是可以实现LRU缓存策略的,前提是你需要将LinkedHashMap中的accessorder属性设置为true。 因此你基本可以认为...
AppComponentesJSF2 JSF 2的大多数可视化组件的简单示例。数组列表集,HashSet,LinkedHashMap,LinkedHashSet的使用
java集合在日常开发中经常用到,对基础的掌握尤其重要,其中List,Set,Map的作用以及使用的场景和分类描述,其中Arraylist 与 LinkedList 区别,HashSet与TreeSet与LinkedHashSet对⽐,LinkedHashMap和HashMap,...
这个库模拟了 Java 的集合框架。 共有 7 个类(ArrayList、HashMap、HashSet、TreeMap、TreeSet、LinkedHashMap、LinkedHashSet)可用。 以更快更有效的方式组织您的 JavaScript 数据。