集合（Set）

以下内容是以数据结构的角度来分析

前言

从数据结构的角度分析：

1. List（列表）：列表是一种有序的数据结构，其中的元素可以重复，并且可以通过索引访问和修改。列表通常用于按照插入顺序存储数据，可以进行元素的添加、删除和修改等操作。
2. Set（集合）：集合是一种无序的数据结构，不允许重复元素。集合通常用于存储唯一的元素，可以执行集合运算（如并集、交集、差集）以及判断元素的存在性。
3. Queue（队列）：队列是一种先进先出（First-In-First-Out，FIFO）的数据结构，它按照元素的插入顺序进行操作。队列通常用于模拟排队或任务调度等场景，支持元素的入队和出队操作。
4. Map（映射或字典）：映射是一种键值对（Key-Value）的数据结构，其中每个键（Key）关联一个值（Value）。映射通常用于存储具有唯一标识符的数据，可以通过键快速查找对应的值。

从 Java 的角度分析：

在 Java 中，List、Set、Queue 和 Map 都可以被称为集合（Collection）。

Java 提供了一个 java.util.Collection 接口，它是所有集合类的根接口。这个接口定义了集合的基本操作和行为，例如添加元素、删除元素、判断元素是否存在等。

List、Set 和 Queue 是 java.util.Collection 接口的子接口，它们分别表示列表、集合和队列的概念，并提供了各自的特定方法和行为。

• List 表示有序的集合，允许重复元素，可以通过索引访问和修改元素。常见的实现类包括 ArrayList 和 LinkedList。
• Set 表示无序的集合，不允许重复元素。常见的实现类包括 HashSet、LinkedHashSet 和 TreeSet。
• Queue 表示队列，是一种先进先出（FIFO）的数据结构。常见的实现类包括 LinkedList 和 PriorityQueue。

另外，Map 是一个独立于 Collection 的接口，它表示键值对的映射关系。Map 接口提供了根据键快速查找值的功能。常见的实现类包括 HashMap、LinkedHashMap 和 TreeMap。

集合的特点

1. 不存放重复的元素
2. 常用于去重
   • 存放新增 IP，统计新增 IP 量
   • 存放词汇，统计词汇量

思考：集合的内部实现能否直接利用以前学过的数据结构？

可以用以下几种方式：

• 动态数组
• 链表
• 二又搜索树(AVL树、红黑树)

Set 接口

public interface Set<E> {
	int size();
	boolean isEmpty();
	void clear();
	boolean contains(E element);
	void add(E element);
	void remove(E element);
  /**
	 * 遍历
	 * @param visitor
	 */
	void traversal(Visitor<E> visitor);
	
	public static abstract class Visitor<E> {
		boolean stop;
		// 如果返回true，就代表停止遍历
		public abstract boolean visit(E element);
	}
}

用链表实现 - ListSet

public class ListSet<E> implements Set<E> {
  
	private List<E> list = new LinkedList<>();
	
	@Override
	public int size() {
		return list.size();
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	@Override
	public void clear() {
		list.clear();
	}

	@Override
	public boolean contains(E element) {
		return list.contains(element);
	}

	@Override
	public void add(E element) {
		int index = list.indexOf(element);
		if (index != List.ELEMENT_NOT_FOUND) { // 索引存在就覆盖
			list.set(index, element);
		} else { // 不存在就添加
			list.add(element);
		}
	}

	@Override
	public void remove(E element) {
		int index = list.indexOf(element);
		if (index != List.ELEMENT_NOT_FOUND) {
			list.remove(index);
		}
	}

	@Override
	public void traversal(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		
		int size = list.size();
		for (int i = 0; i < size; i++) {
			if (visitor.visit(list.get(i))) {
				return;
			}
		}
	}

用红黑树实现 - TreeSet

public class TreeSet<E> implements Set<E> {
	private RBTree<E> tree;
	
	public TreeSet() {
		this(null);
	}
	
	public TreeSet(Comparator<E> comparator) {
		tree = new RBTree<>(comparator);
	}
	
	@Override
	public int size() {
		return tree.size();
	}

	@Override
	public boolean isEmpty() {
		return tree.isEmpty();
	}

	@Override
	public void clear() {
		tree.clear();
	}

	@Override
	public boolean contains(E element) {
		return tree.contains(element);
	}

	@Override
	public void add(E element) {
		tree.add(element);
	}

	@Override
	public void remove(E element) {
		tree.remove(element);
	}

	@Override
	public void traversal(Visitor<E> visitor) {
		// 中序遍历，元素从小到大排序
		tree.inorder(new BinaryTree.Visitor<E>() {
			@Override
			public boolean visit(E element) {
				return visitor.visit(element);
			}
		});
	}

}

遍历测试

public class Main {

	// 遍历测试
	static void test1() {

		Set<Integer> listSet = new ListSet<>();
		listSet.add(10);
		listSet.add(11);
		listSet.add(11);
		listSet.add(12);
		listSet.add(10);
		
		Set<Integer> treeSet = new TreeSet<>();
		treeSet.add(12);
		treeSet.add(10);
		treeSet.add(7);
		treeSet.add(11);
		treeSet.add(10);
		treeSet.add(11);
		treeSet.add(9);
		
		treeSet.traversal(new Visitor<Integer>() {
			@Override
			public boolean visit(Integer element) {
				System.out.println(element);
				return false;
			}
		});
	}

	public static void main(String[] args) {
		test1();
	}

}

复杂度分析

• ListSet 是基于链表实现的，添加、删除、搜索都是 O(n) 级别。
• TreeSet 是基于红黑树实现的，添加、删除、搜索都是 O(logn) 级别。

链表找元素时，最坏的情况是 O(n)

性能对比

了解一下，复制路径时 \ 变成 \\ 是转义。

阅读 jdk 中的 src\java\util 目录下后缀名为 java 的文件。

文件阅读器

参考笔者此篇文章：手写一个文件阅读器 (opens new window)

运行耗时计算器

参考笔者此篇文章：手写一个运行耗时计算器 (opens new window)

方法测试

public class Main {
		
	static void testSet(Set<String> set, String[] words) {
		// 添加
		for (int i = 0; i < words.length; i++) {
			set.add(words[i]);
		}
		// 搜索
		for (int i = 0; i < words.length; i++) {
			set.contains(words[i]);
		}
		// 删除
		for (int i = 0; i < words.length; i++) {
			set.remove(words[i]);
		}
	}
	
	static void test2() {
		FileInfo fileInfo = Files.read("C:\\Program Files\\Java\\jdk1.8.0_321\\src\\java\\util",
				new String[]{"java"});
		
		System.out.println("文件数量：" + fileInfo.getFiles());
		System.out.println("代码行数：" + fileInfo.getLines());
		String[] words = fileInfo.words();
		System.out.println("单词数量：" + words.length);

		Set<String> listSet = new TreeSet<>();
		for (String word : words) {
			listSet.add(word);
		}
		System.out.println("词汇量：" + listSet.size());

		RuntimeCalculator.test("ListSet", new Task() {
			@Override
			public void execute() {
				testSet(new ListSet<>(), words);
			}
		});
		
		RuntimeCalculator.test("TreeSet", new Task() {
			@Override
			public void execute() {
				testSet(new TreeSet<>(), words);
			}
		});
	}

	public static void main(String[] args) {
		test2();
	}

}

运行结果

文件数量：364
代码行数：211995
单词数量：877191
词汇量：17170
【ListSet】
开始：16:39:43.458
结束：16:40:23.027
耗时：39.569秒
-------------------------------------
【TreeSet】
开始：16:40:23.028
结束：16:40:23.467
耗时：0.439秒
-------------------------------------

进程已结束,退出代码0

总结

显然 TreeSet 的性能比 ListSet 好很多，链表实现的集合性能太差。

TreeSet 的局限性

使用红黑数也就是二叉搜索数来实现集合的话，会有一个限制（前提条件）：

• 元素必须具备可比较性

如果希望加进去的元素是没有可比较性的，也希望提升这个性能，也希望能达到红黑树这样级别，效率特别高。那怎么办呢？

答案：可以使用哈希表。

练习

349. 两个数组的交集 - 力扣（LeetCode） (opens new window)