关注“Java后端技术全栈”
回复“面试”获取全套面试资料
Set继承于Collection接口,是一个不允许出现重复元素,并且无序的集合,主要有HashSet和TreeSet两大实现类,另外LinkedHashSet也有一定的使用频率。
在判断重复元素的时候,Set集合会调用hashCode()和equal()方法来实现。
与List一样都是接口,Set接口也提供了集合操作的基本方法。Java四大集合之一,但与List不同的是,Set还提供了equals(Object o)和hashCode(),供其子类重写,以实现对集合中插入重复元素的处理;
public interface Set<E> extends Collection<E> {
//添加
boolean add(E e);
boolean addAll(Collection<? extends E> c);
//删除
boolean remove(Object o);
boolean removeAll(Collection<?> c);
void clear();
//长度
int size();
//是否为空
boolean isEmpty();
//是否包含
boolean contains(Object o);
boolean containsAll(Collection<?> c);
boolean retainAll(Collection<?> c);
//获取Set集合的迭代器:
Iterator<E> iterator();
//把集合转换成数组
Object[] toArray();
<T> T[] toArray(T[] a);
//判断元素是否重复,为子类提高重写方法
boolean equals(Object o);
int hashCode();
}
接口里知识定义了方法,具体的实现请看下面两个常用实现类。
HashSet 是用来存储没有重复元素的集合类,并且是无序的。实现了 Set 接口。底层其实主要是使用 HashMap 机制实现,所以也是线程不安全。
部分源码:
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
private transient HashMap<E,Object> map;
//这里这个PRESENT就是作为HashMap中的key
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
特征:
使用场景:去重、不要求顺序
原理:HashSet底层由HashMap实现,插入的元素被当做是HashMap的key,根据hashCode值来确定集合中的位置,由于Set集合中并没有角标的概念,所以并没有像List一样提供get()方法。当获取HashSet中某个元素时,只能通过遍历集合的方式进行equals()比较来实现;
常用方法
//添加
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//移除
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//清空
public void clear() {
map.clear();
}
//获取迭代器
public Iterator<E> iterator() {
return map.keySet().iterator();
}
//判断是否为空
public boolean isEmpty() {
return map.isEmpty();
}
//求集合大小
public int size() {
return map.size();
}
正如上面所说,底层使用 HashMap 的 key 不能重复机制来实现没有重复的 HashSet。
TreeSet 实现了 SortedSet 接口,意味着可以排序,它是一个有序并且没有重复的集合类,底层是通过 TreeMap 实现。TreeSet 并不是根据插入的顺序来排序,而是字典自然排序。线程不安全。从名字上可以看出,此集合的实现和树结构有关。与HashSet集合类似,TreeSet也是基于Map来实现,具体实现TreeMap(后面讲解),其底层结构为红黑树(特殊的二叉查找树)。
TreeSet 支持两种排序方式:自然升序排序和自定义排序。
部分源码
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
常用方法
//求集合大小
public int size() {
return m.size();
}
//判断是否为空
public boolean isEmpty() {
return m.isEmpty();
}
//判断是否包含
public boolean contains(Object o) {
return m.containsKey(o);
12 }
特征:
原理:
TreeSet 底层是基于 treeMap(红黑树结构)实现的,可以自定义比较器对元素进行排序,或是使用元素的自然顺序。
使用场景:去重、要求排序
LinkedHashSet 是使用 HashSet 机制实现,它是一个可以保证插入顺序或是访问顺序,并且没有重复的集合类。线程不安全。
数据结构:数组 + 双向链表,Entry 结构:before|hash|key|value|next|after,before 和 after 用于维护整个双向链表。
部分源码
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
常用方法
从这里可以看出,这家伙基本上都是使用HashSet来实现的,所以常用方法和HashSet相同。
特征:
原理:
LinkedHashSet 底层使用了 LinkedHashMap 机制(比如 before 和 after),加上又继承了 HashSet,所以可以实现既可以保证迭代顺序,又可以达到不出现重复元素。
使用场景:去重、需要保证插入或者访问顺序