【数据结构】Set的使用与注意事项

Set 的使用

Set 与 Map 主要的不同有两点：Set 是继承自 Collection 的接口类，Set 中只存储了 Key

	方法	解释
	boolean add(E e)	添加元素，但重复元素不会被添加成功
	void clear()	清空集合
	boolean contains(Object o)	判断 o 是否在集合中
	Iterator iterator()	返回迭代器
	boolean remove(Object o)	删除集合中的 o
	int size()	返回set中元素的个数
	boolean isEmpty()	检测set是否为空，空返回true，否则返回false
	Object[] toArray()	将set中的元素转换为数组返回
	boolean containsAll(Collection c)	集合c中的元素是否在set中全部存在，是返回true，否则返回 false
	boolean addAll(Collection c)	将集合c中的元素添加到set中，可以达到去重的效果

add()

Set<String> set = new TreeSet<>();  
set.add("abc");  
set.add("hello");  
set.add("abc");  
System.out.println(set);/*
[abc, hello]
*/

• 可发现，set 中不能存储相同的元素

---

iterator()

通过迭代器返回集合

Set<String> set = new TreeSet<>();  
set.add("abc");  
set.add("hello");  
set.add("abc");  Iterator<String> it =  set.iterator();  
while (it.hasNext()){  System.out.println(it.next());  
}/*
abc
hello
*/

• while 判断 it 是否还有下一个，有的话就打印，打印完后就到下一个

注意事项

1. Set 是继承自 Collection 的一个接口类

2. Set 中只存储了 key，并且要求 key 一定要唯一

3. TreeSet 的底层是使用 Map 来实现的，其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的

4. Set 最大的功能就是对集合中的元素进行去重

5. 实现 Set 接口的常用类有 TreeSet 和 HashSet，还有一个 LinkedHashSet，LinkedHashSet是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序。

6. Set 中的 Key 不能修改，如果要修改，先将原来的删除掉，然后再重新插入

7. TreeSet 中不能插入 null 的 key，HashSet 可以

	Set 底层结构	TreeSet	HashSet
	底层结构	红黑树	哈希桶
	插入/删除/查找时间 复杂度	$O(logN)$	$O(1)$
	是否有序	关于Key有序	不一定有序
	线程安全	不安全	不安全
	插入/删除/查找区别	按照红黑树的特性来进行插入和删除	1. 先计算key哈希地址 2. 然后进行 插入和删除
	比较与覆写	key必须能够比较，否则会抛出 ClassCastException异常	自定义类型需要覆写equals和 hashCode方法
	应用场景	需要Key有序场景下	Key是否有序不关心，需要更高的 时间性能