Set实现（2）| LinkedHashSet

1. LinkedHashSet的适用范围

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

2. 源码分析与实例

2.1 内部结构

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

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

2.2 添加元素

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

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

2.3 删除元素

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

java">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)方法时，以下步骤发生：

从HashMap中删除：首先，HashMap的remove(Object key)方法会被调用，以删除指定的键和对应的值。如果成功找到并删除了键值对，remove方法会返回true；否则返回false。
从双向链表中删除：如果元素存在于集合中（即HashMap的remove方法返回true），接下来会从双向链表中移除对应的Entry节点。这通过更新被删除节点的前一个节点和后一个节点的prev和next引用来完成。具体来说：
- 将被删除节点的前一个节点的next引用设置为被删除节点的后一个节点。
- 将被删除节点的后一个节点的prev引用设置为被删除节点的前一个节点。
维护插入顺序：由于LinkedHashSet需要保持元素的插入顺序，因此在添加新元素时，新Entry总是添加到双向链表的尾部。相应地，在删除元素时，只需要修改相邻节点的引用，而不需要重新排序链表。
清理工作：如果被删除的元素是LinkedHashSet中的最后一个元素，还需要从双向链表中移除对应的Entry节点。

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

2.4 检查元素

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

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

2.5 示例

java">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")); // trueSystem.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是一个很好的选择。