Set实现（2）| LinkedHashSet

1. LinkedHashSet的适用范围

• 去重并保持顺序：当你需要存储不重复的元素，并且希望保持它们的插入顺序时，如购物车中的商品、历史记录等。
• 有序集合：如果元素的顺序很重要，可以使用LinkedHashSet。
• 快速访问：如果你需要频繁地进行添加、删除和检查操作，LinkedHashSet是一个很好的选择。

2. 源码分析与实例

2.1 内部结构

LinkedHashSet的内部是基于一个HashMap实例和一个双向链表。所有的元素实际上是作为HashMap的键来存储的，而双向链表则用于维护元素的插入顺序。

private static class Entry<E> extends HashMap.Entry<E,Object> {
    Entry<E> prev;
    Entry<E> next;
    ...
}

2.2 添加元素

add方法通过调用内部的HashMap的put方法来添加元素。如果put返回null，则说明之前没有这个元素，因此添加成功。同时，新元素会被添加到双向链表的末尾。

public boolean add(E e) {
    if (e == null) return false;
    return map.put(e, PRESENT)==null;
}

2.3 删除元素

remove方法首先检查传入的对象是否为null，然后调用HashMap的remove方法来删除元素。同时，从双向链表中移除对应的节点。

public boolean remove(Object o) {
    if (o==null) return false;
    return map.remove(o)!=null;
}

在LinkedHashSet中，每个元素都存储在一个内部类Entry的实例中，该内部类扩展了HashMap.Entry。除了作为HashMap中的键值对，每个Entry还包含两个额外的属性：一个指向前一个Entry的引用（prev），和一个指向后一个Entry的引用（next）。这样，所有的Entry对象形成一个双向链表。

当调用remove(Object o)方法时，以下步骤发生：

1. 从HashMap中删除：首先，HashMap的remove(Object key)方法会被调用，以删除指定的键和对应的值。如果成功找到并删除了键值对，remove方法会返回true；否则返回false。

2. 从双向链表中删除：如果元素存在于集合中（即HashMap的remove方法返回true），接下来会从双向链表中移除对应的Entry节点。这通过更新被删除节点的前一个节点和后一个节点的prev和next引用来完成。具体来说：

   • 将被删除节点的前一个节点的next引用设置为被删除节点的后一个节点。
   • 将被删除节点的后一个节点的prev引用设置为被删除节点的前一个节点。

3. 维护插入顺序：由于LinkedHashSet需要保持元素的插入顺序，因此在添加新元素时，新Entry总是添加到双向链表的尾部。相应地，在删除元素时，只需要修改相邻节点的引用，而不需要重新排序链表。

4. 清理工作：如果被删除的元素是LinkedHashSet中的最后一个元素，还需要从双向链表中移除对应的Entry节点。

通过这种方式，LinkedHashSet能够在常数时间内删除元素，同时保持其有序性。由于每个元素都是通过双向链表连接的，因此即使元素从HashMap中删除，双向链表也能够保持其完整性。这使得LinkedHashSet在迭代时能够按照元素的插入顺序进行访问。

2.4 检查元素

contains方法根据传入的对象是否为null，分别调用HashMap的containsValue和containsKey方法。

public boolean contains(Object o) {
    return (o==null ? map.containsValue(PRESENT) : map.containsKey(o));
}

2.5 示例

import java.util.LinkedHashSet;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        // 创建一个LinkedHashSet实例
        LinkedHashSet<String> set = new LinkedHashSet<>();

        // 添加元素
        set.add("Alice");
        set.add("Bob");
        set.add("Charlie");
        set.add(null); // 允许添加null元素，但只能有一个

        // 检查元素
        System.out.println("Contains 'Alice': " + set.contains("Alice")); // true
        System.out.println("Contains 'David': " + set.contains("David")); // false

        // 删除元素
        set.remove("Alice");
        System.out.println("After removing 'Alice': " + set); // [Bob, Charlie]

        // 遍历元素
        for (String name : set) {
            System.out.println(name);
        }
    }
}

3. 总结

LinkedHashSet是Java集合框架中的一个非常有用的类，它通过内部的HashMap和双向链表实现了快速的添加、删除和查询操作。在使用LinkedHashSet时，需要注意其不保证元素的顺序，并且不能存储重复的元素。在需要去除重复元素且关心元素顺序的场景下，LinkedHashSet是一个很好的选择。