LinkedHashSet详解(定义特点及原理使用)

LinkedHashSet定义

LinkedHashSet是Java集合框架中的一种Set实现类，它继承了HashSet类并实现了Set接口，同时内部使用链表来维护元素的顺序。

 

LinkedHashSet特点

LinkedHashSet具有以下特点：

1.元素有序

与HashSet不同，LinkedHashSet中的元素是有序的，它会按照元素被添加的顺序来维护元素的顺序。

 

2.不允许重复元素

与HashSet类似，LinkedHashSet也不允许集合中存在重复的元素，如果添加重复元素，只会保留一个。

 

3.具有HashSet的高效性能

LinkedHashSet底层使用了哈希表来存储元素，因此可以在O(1)的时间复杂度内执行插入、删除和查找操作。

 

4.支持迭代器

LinkedHashSet提供了iterator()方法，可以返回一个迭代器，可以用于遍历集合中的元素。

 

5.线程不安全

与HashSet类似，LinkedHashSet是线程不安全的，如果多个线程同时访问同一个LinkedHashSet实例，需要采取适当的同步措施。

 

LinkedHashSet原理

LinkedHashSet是Java集合框架中的一种Set实现类，它的底层数据结构是一个哈希表和一个双向链表。

如下图所示：

当向LinkedHashSet中添加元素时，首先会计算元素的哈希值，然后根据哈希值定位到对应的哈希槽，如果该槽中没有元素，则将新元素添加到该槽中。

如果该槽中已经有元素，那么就需要判断新元素是否与已有元素相等，如果相等，则不进行添加，否则，将新元素添加到该槽对应的链表的末尾。

LinkedHashSet的实现原理和HashSet类似，不同之处在于LinkedHashSet内部维护了一个双向链表，以保持元素的顺序。

LinkedHashMap额外维护了一个双向链表，在在每次插入数据，或者访问、修改数据时，会对这个双向链表增加节点、或调整链表的节点顺序，从而保证这个有序性。

因此，在性能上可能会比HashSet稍慢一些，但是可以保持元素的插入顺序。

 

LinkedHashSet使用

LinkedHashSet的常用方法与HashSet类似，包括：

1. add(Object obj)：将指定的元素添加到集合中。
2. remove(Object obj)：从集合中删除指定的元素。
3. contains(Object obj)：判断集合中是否包含指定的元素。
4. size()：返回集合中元素的数量。
5. clear()：清空集合中的元素。
6. iterator()：返回一个迭代器，可以用于遍历集合中的元素。

下面是一个使用LinkedHashSet来实现LRU缓存的例子：

import java.util.LinkedHashSet;

public class LRUCache<K> {
    private LinkedHashSet<K> set;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        set = new LinkedHashSet<K>(capacity);
    }

    public void put(K key) {
        if (set.contains(key)) {
            set.remove(key);
        } else if (set.size() == capacity) {
            K firstKey = set.iterator().next();
            set.remove(firstKey);
        }
        set.add(key);
    }

    public boolean contains(K key) {
        return set.contains(key);
    }
}

在上面的例子中，LRUCache类使用LinkedHashSet来存储最近访问的数据，当缓存满了之后，使用迭代器获取链表的头部元素进行删除，实现了LRU算法。

 

LinkedHashSet应用场景

LinkedHashSet可以用于需要保持元素顺序的场景，例如：

1. 缓存中存储最近访问的数据：当缓存中的数据达到一定的大小时，可以使用LinkedHashSet来保留最近访问的数据，当缓存满了之后，可以从链表的头部开始删除最旧的数据。
2. 保存按照顺序生成的数据：当需要按照顺序生成一些数据并进行保存时，可以使用LinkedHashSet来保留生成的数据的顺序，避免在后续处理时需要进行排序操作。

作者简介

陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号，获取更多技术干货！

后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》