前言
大家好啊,我是汤圆,明天给大家带来的是《Java 中的汇合 Set – 入门篇》,心愿对大家有帮忙,谢谢
简介
后面介绍了汇合 List,映射 Map,最初再简略介绍下汇合Set
,相干类如下图所示
注释
Set 从里面看像 List(都是存储繁多数据的汇合),只不过 存储的数据不会有反复 ;
然而外面却是 Map 映射(因为它内存存储是基于 Map 构造实现),这也是为什么把 Set 放到 Map 前面来说的起因。
Set 和 Map 有什么关系呢?
因为 Map 的键不会有反复,所以 Set 就利用了 Map 的这个特点,将其作为外部成员变量来应用
比方咱们看下 HashSet 外部的源码,能够看到,基本上所有操作都是基于其外部的成员变量 HashMap 进行的
private transient HashMap<E,Object> map;
// 这个常量只是为了适配 Map 的键值对构造,无实际意义
private static final Object PRESENT = new Object();
public HashSet() {map = new HashMap<>();
}
public int size() {return map.size();
}
public boolean contains(Object o) {return map.containsKey(o);
}
public boolean add(E e) {return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {return map.remove(o)==PRESENT;
}
Set 的品种
Set 的品种相似 Map
Set 次要有三种类型:HashSet(罕用)、TreeSet(树形构造)、LinkedHashSet(前两者的联合)
咱们先来看一下 Set 接口次要的几个办法:
boolean add(E e)
:往 Set 中增加元素boolean contains(Object o)
:查问 Set 是否蕴含指定对象boolean remove(Object o)
:从 Set 中删除指定对象int size()
:返回 Set 的元素数量
上面咱们简略看下三者的区别
HashSet | TreeSet | LinkedHashSet | |
---|---|---|---|
访问速度 | 快 | 慢 | 适中 |
元素是否有序 | 无序 | 有序,默认升序 | 有序,默认按插入的程序 |
实用场景 | 为疾速查问而设计(用的最多) | 须要排序的场景 | 须要保障查问和插入程序统一的场景 |
接下来咱们以 HashSet 为例,来介绍 Set 接口
HashSet
HashSet 是一个无序汇合
因为它外部是基于 HashMap 实现
下面的源码咱们有看到,HashSet 每插入一个元素,就将该元素作为外部 hashMap 的 key,而后常量 Object 作为 hashMap 的 value,存储到 hashMap 中
- 如果元素的 hash 值没有反复,就依照数组的形式顺次排列;
- 如果 hash 值有反复的,就增加到已有的值对前面,造成链表构造;
整体构造 如下图所示
上面用代码示范一下
public class SetDemo {public static void main(String[] args) {
// 初始化
Set<Integer> set = new HashSet<>();
// 增加元素
set.add(10);
// 元素数量
int size = set.size();
System.out.println(size);
// 查问元素是否存在
boolean isContain = set.contains(10);
System.out.println(set);
// 删除
set.remove(10);
System.out.println(set);
}
}
TreeSet
TreeSet 在插入的时候,能够依照元素进行排序(默认升序)
它适宜用在排序比拟多的场景,性能会比 HashSet 差一些
上面用代码示范一下(重点要来了)
public class SetDemo {public static void main(String[] args) {
// TreeSet
B b = new B();
// 初始化
Set<B> set2 = new TreeSet<>();
// 增加元素
set2.add(b);
// 元素数量
int size2 = set2.size();
System.out.println(size2);
// 查问元素是否存在
boolean isContain2 = set2.contains(b);
System.out.println(set2);
// 删除
set2.remove(b);
System.out.println(set2);
}
}
class B{
}
这段代码看似一切正常,实则 暗藏玄机
如果你运行这段代码,会报出上面的 谬误提醒:类 B 不能转换为 Comparable。
可是为什么要转换呢?我也没有转换啊
那是因为外部主动转换了
TreeSet 啥时候会主动将元素类转为 Comparable 呢?
是在你插入第一个数据开始,外部就曾经开始在做比拟了(第一次先本人跟本人做比拟,目标就是查看你这个数据有没有实现 Comparable 接口);
前面每插一个数据,都要从根节点开始挨个比拟排序
这其实也算也是 TreeSet 外部排序的工作原理
所以下面这段代码须要让 B 实现 Comparable 接口,改后如下所示
public class SetDemo {public static void main(String[] args) {
// TreeSet
B b = new B();
// 初始化
Set<B> set2 = new TreeSet<>();
// 增加元素
// 此时运行没问题
set2.add(b);
// 元素数量
int size2 = set2.size();
System.out.println(size2);
// 查问元素是否存在
boolean isContain2 = set2.contains(b);
System.out.println(set2);
// 删除
set2.remove(b);
System.out.println(set2);
}
}
// 这里实现了 Comparable
class B implements Comparable{
@Override
public int compareTo(Object o) {return this.hashCode()>o.hashCode() ? 1 : -1;}
}
此时运行就没问题了
那为什么 TreeMap 没有这个问题呢?
其实 TreeMap 也有这个问题,只是 TreeMap 的键 key 个别都是字符串或者整型,而字符串和整型对象外部曾经实现了 Comparable 接口,所以问题不大(因为用自定义对象做键 key 的毕竟还是多数)
LinkedHashSet
LinkedHashSet 领有 HashSet 的大部分长处,且保障了插入的程序,使得在查问的时候,能够依照插入的程序顺次读取(原理是链表)
这里要留神一点:在 Java 程序语言设计中,所有的链表都是双向链表,即每个节点还寄存着一个指向前节点的援用
大抵的结构图如下所示(之前的 LinkedHashMap 遗记贴图了,跟这个相似,只是元素内容不同):
三者的排序比拟
参考上一篇映射 Map,Set 排序比拟体现进去的行为与 Map 统一
总结
Set 个别用到的有 HashSet,TreeSet,LinkedHashSet,外部都是无反复元素
- HashSet 的插入和拜访都很快,然而外部是无序排列
- TreeSet 的插入和拜访都很慢,然而外部是有序排列,默认按升序排列
- LinkedHashSet 领有 HashSet 的大部分长处,而且还能够依照元素插入的程序来拜访元素,然而性能会比 HashSet 差
后记
最初,感激大家的观看,谢谢