【谈谈】Map、Set集合存放是无序的，然而LinkedHashSet和LinkedHashMap等集合却有序，分析原因

约定不等于承诺〃 2022-01-15 22:07 122阅读 0赞

首先，我们必须明确一点，我们这里所谈的有序和无序不是指集合中的排序，而是指是否按照元素添加的顺序来存储对象。

Set（元素不重复的集合）集合的无序性：  
Set集合内元素的存放顺序和hashcode有关，而哈希表是用算法把不同的数据按照规则放在相应的地址，所以其其位置一定。但其输出数据的顺序和用户的存储顺序并不一致，考虑到Set是个接口，接口的契约很单纯，不会做过多的保证。Set的契约重点就是“元素不重复的集合”，而对顺序不做保证（也就是不做限制，有序无序都可以）。实现该接口的类既可以提供有序的实现，也可以提供无序的实现。  
HashSet在保存数据的时候显然还是得按一定顺序放入其背后的数组中，但顺序不是用户可控制的，对用户来说就是“无序”。  
与之相对，SortedSet接口的契约就包含了“元素不重复，且按照用户指定的方式排序的集合”的意义。SortedSet接口满足Set接口的契约，并额外添加的“有序”的契约。TreeSet就是实现了SortedSet（以及Set）接口的实现，它就是有序的。  
LinkedHashSet的有序:  
底层数据结构由哈希表和链表组成。  
哈希表保证元素的唯一性。  
链表保证元素有素。(存储和取出是一致)

LinkedHashSet 的实现  
对于 LinkedHashSet 而言，它继承与 HashSet、又基于 LinkedHashMap 来实现的。  
LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同，因此 LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。  
需要注意理解的点是：  
LinkedHashSet 是 Set 的一个具体实现，其维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。  
LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的（具体的区别大家可以自己去思考一下）。  
如果我们需要迭代的顺序为插入顺序或者访问顺序，那么 LinkedHashSet 是需要你首先考虑的。

Map集合的无序性：  
Map是无序的，它的存储结构是哈希表<key,value>键值对，map中插入元素是根据key计算出的哈希值来存储元素的，因此他不是按照元素的添加顺序来存储对象的，所以Map是无序的。它的实现类有：HashMap、TableMap和TreeMap。这些都是无序的。  
LinkedHashMap的有序:  
是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。  
由哈希表保证键的唯一性  
由链表保证键盘的有序(存储和取出的顺序一致)  
LinkedHashMap是HashMap的子类，很多方法都是继承自父类，重要的区别就是内部类中多了两个entry,一个记录前方entry，一个记录后方entry，这样的双向链表结构保证了插入顺序的有序。  
总得来说，LinkedHashMap底层是数组加单项链表加双向链表。然后LInkedHashMap重写了两个方法，一个是添加entry，一个是创建entry，这两种时刻都要维护双向链表。

/**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    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);
        }
    }

可以看到LinkedHashMap.Entry 继承自HashMap.Node 除了Node 本身有的几个属性外，额外增加了before after 用于指向前一个Entry 后一个Entry。也就是说，元素之间维持着一条总的链表数据结构。正式因为这个链表才保证了LinkedHashMap的有序性。

双向链表：转自https://blog.csdn.net/weixin\_45023089/article/details/91388607  
双向链表是链表的一种，它的每个数据节点都有两个指针分别指向直接后继和直接前驱，所以从双向链表的任意一个节点开始都可以很方便的访问它的前驱节点和后继节点。这是双向链表的优点，缺点是每个节点都需要保存当前节点的next和prev两个属性，这样才能保证优点。所以需要更多的内存开销，并且删除和添加也会比较费时间。

下图是双向链表的节点:  
prve指向上一个结点，next指向下一个结点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]  
多个节点相互连接，保证了数据录入的顺序。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]: /images/20220115/d5f67691ca4746f6898473d7d1c3215d.png