8.Java容器-Set详解
本文主要讲Set的三个子类: HashSet:底层数据结构是哈希表(是一个元素为链表的数组) + 红黑树; TreeSet集合:1.底层数据结构是红黑树(是一个自平衡的二叉树);2.保证元素的排序方式; LinkedHashSet集合:底层数据结构由哈希表(是一个元素为链表的数组)和双向链表组成;HashSet 1.实现Set接口;
本文主要讲Set的三个子类:
HashSet:底层数据结构是哈希表(是一个元素为链表的数组) + 红黑树;
TreeSet集合:1.底层数据结构是红黑树(是一个自平衡的二叉树);2.保证元素的排序方式;
LinkedHashSet集合:底层数据结构由哈希表(是一个元素为链表的数组)和双向链表组成;
HashSet
1.实现Set接口;
2.不保证迭代顺序;
3.允许元素为null;
4.底层实际上是一个HashMap实例,操作HashSet元素实际上就是操作HashMap;
5.非同步;
6.初始容量非常影响迭代性能,如果很重视遍历的性能,不要将初始容量设置地太大;
HashSet的属性和构造函数
//从这可以看出,HashSet的底层其实就是一个HashMap
private transient HashMap<E,Object> map;
// HashMap是<key,value>映射,既然HashSet底层用的是HashMap,那么value在哪里呢?
// value是一个Object,所有的value都是它
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
TreeSet
1.实现NavigableSet接口;
2.可以实现排序功能,Comparable或自定义的Comparator
3.底层实际上是一个TreeMap实例;
4.非同步;
5.方法的时间复杂度为log(n);
private transient NavigableMap<E,Object> m;
// Map的value
private static final Object PRESENT = new Object();
/**
* Constructs a set backed by the specified navigable map.
*/
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
//底层实现是TreeMap
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
LinkedHashSet
4.非同步;
5.性能比HashSet差一点,因为要维护一个双向链表;
6.遍历与初始容量无关,遍历的是双向链表;
总结
Set集合的底层就是Map;
HashSet:无序,允许为null,底层是HashMap(散列表+红黑树),非线程同步;
TreeSet:有序,不允许为null,底层是TreeMap(红黑树),非线程同步;
LinkedHashSet:迭代有序,允许为null,底层是HashMap+双向链表,非线程同步;
参考
https://zhuanlan.zhihu.com/p/29021276
https://blog.csdn.net/panweiwei1994/article/details/76555359
https://zhongfucheng.bitcron.com/post/javaji-chu/setji-he-jiu-zhe-yao-jian-dan-!
更多推荐
所有评论(0)