java之集合—Set、HashSet、TreeSet详解
文章目录
java之集合---Set、HashSet、TreeSet详解一、Set1.1 概念1.2 方法
二、HashSet2.1 概念2.2 哈希表
三、TreeSet3.1 概念3.2 二叉查找树3.3 Comparable 和 Comparator
总结
一、Set
1.1 概念
Set是Collection接口的子接口，是集合的规范之一。 特点：无序、无下标、元素不可重复。 Set的实现类有：HashSet、LinkedHashSet、TreeSet 由于Set是接口，不能直接实现，只能通过向上转型的方式创建对象，以HashSet为例：
Set set = new HashSet();//通过向上转型的方式创建对象
1.2 方法
Set继承了Collection接口，其拥有的方法继承自Collection接口，此处不再赘述，如想了解请移步：java之集合–Collection父接口及其方法
二、HashSet
2.1 概念
HashSet是Set接口的实现类之一，其存储结构为哈希表。 特点：存储结构为哈希表，通过计算元素的哈希值（hashCode）来为其分配存储空间。
由于HashSet是具体类，可以直接创建对象：
HashSet set = new HashSet();
2.2 哈希表
哈希表是一种存储结构，在java中，其结构可大致看为：数组+链表。 以下面的元素为例：
[a，b，c，d，e，f]
我们的任务是通过哈希表将上述序列存起来。 a是第一个元素，先获取a的哈希值，之后通过计算为其分配位置。（哈希值的计算我们下次再讲，主要领会流程） a存储之后，下一个是b，先获取b的哈希值，之后通过计算为其分配位置。 b存储之后，下一个是c，先获取c的哈希值，发现计算后c的位置与a的一样，开始进行判断。 a.equals©：判断元素是否相同 若相同，拒绝此元素加入 若不同，元素c作为a的指向，与a形成链表结构： c存储之后，下一个是d，先获取d的哈希值，之后通过计算为其分配位置。 d存储之后，下一个是e，先获取e的哈希值，发现计算后e的位置与a的一样，开始进行判断。 a.equals(e)：判断元素是否相同 若相同，拒绝此元素加入 若不同，元素c作为a的指向，但是c已经是a的指向了，继续判断： c.equals(e)：判断元素是否相同 若相同，拒绝此元素加入 若不同，元素e作为c的指向，与c形成链表结构： e存储之后，下一个是f，先获取f的哈希值，发现计算后e的位置与b的一样，开始进行判断。 b.equals(f)：判断元素是否相同 若相同，拒绝此元素加入 若不同，元素f作为b的指向，与b形成链表关系： 至此，所有元素都存入了哈希表中。
数组的优点：查找快。 缺点：增删慢，长度固定
链表的优点：增删快。 缺点：查找慢
哈希表这种数组+链表的结构，融合了两者的优点，同时也弥补了各自的不足。、
三、TreeSet
3.1 概念
TreeSet是Set接口的实现类之一，其存储结构为红黑树（平衡二叉查找树）。
3.2 二叉查找树
了解红黑树之前，我们先了解一下二叉查找树。 特点：比根节点小的数放在根节点左边，比根节点大的数放在根节点右边。 以下面的序列为例：
[10，5，18，3，21，19，4，59，33，9]
上述序列没有重复元素，我们的任务是通过二叉查找树的特点将其存起来。 10作为序列的起始点，将其作为根节点表示。 接下来是5，5小于10，所以存在10的左边。 5之后是18，18大于10，所以存在10的右边。 注意：每次存数时，都是从根节点（10）开始检查！ 18之后是3，3小于10，所以存在10左边。 10的左边有元素5了，继续判断，3小于5，所以存在5的左边。 3之后是21，21大于10，所以存在10的右边。 10的右边有元素18了，继续判断，21大于18，所以存在18的右边。 21之后是19，19大于10，所以存在10的右边。 10的右边有元素18了，继续判断，19大于18，所以存在18的右边。 18的右边有元素21了，继续判断，19小于21，所以存在21的左边。 19之后是4，4小于10，所以存在10的左边。 10的左边有元素5了，继续判断，4小于5，所以存在5的左边。 5的左边有元素3了，继续判断，4大于3，所以存在3的右边。 4之后是59，59大于10，所以存在10的右边。 10的右边有元素18了，继续判断，59大于18，所以存在18的右边。 18的右边有元素21了，继续判断，59大于21，所以存在21的右边。 59之后是33，33大于10，所以存在10的右边。 10的右边有元素18了，继续判断，33大于18，所以存在18的右边。 18的右边有元素21了，继续判断，33大于21，所以存在21的右边。 21的右边有元素59了，继续判断，33小于59，所以存在59的左边。 33之后是9，9小于10，所以存在10的左边。 10的左边有元素5了，继续判断，9大于5，所以存在5的右边。 9之后没有元素了，序列存储完毕。 以上的图片演示，是一棵二叉查找树建立的完整过程。
为什么会存在这种看起来很麻烦的存储方式呢？
树，是一种数据结构，二叉查找树是树的其中一种表现形式。
树存在三种遍历方式：前序遍历、中序遍历、后序遍历。
其中的前、中、后指的都是根节点的位置。
前序遍历：根，左，右 中序遍历：左，根，右 后序遍历：左，右，根
由于篇幅限制，想要了解中序遍历的朋友，请移步：【数据结构】树—中序遍历
二叉查找树经过中序遍历后，遍历出来的数据是排好序的。将上图中的树经过中序遍历后，得到的序列为：
[3，4，5，9，10，18，19，21，33，59]
对比之前毫无顺序的数据，还是排序的更一目了然。 但这并不是红黑树，红黑树是平衡二叉查找树，不过了解二叉查找树是了解平衡二叉查找树的基础，在以后我会讲解。
3.3 Comparable 和 Comparator
很多新手在使用TreeSet存储数据时，往往编译时会报错：
Student stu = new Student("张三","男",18);
TreeSet set = new TreeSet();
set.add(stu);
System.out.println(set);
错误： 这是因为TreeSet是红黑树的存储结构，需要指定排序。针对这种问题，有两种解决方式： １．令元素的类实现接口Comparable，并重写CompareTo方法：
public class Student implements Comparable{
String name;
String gender;
int age;
@Override
public int compareTo(Object o) {//重写方法
//1代表顺序颠倒；0代表是相同元素，不载入；-1代表不更改顺序。
return 0;
}
public Student(String name, String gender, int age) {
this.name = name;
this.gender = gender;
this.age = age;
}
}
2.创建实现比较器：Comparator接口的类，并重写compare方法。 此处以静态匿名类示范：
Comparator cmp = new Comparator(){
@Override
public int compare(Object o1, Object o2) {
Student stu1 = (Student) o1;
Student stu2 = (Student) o2;
if(stu1.age > stu1.age)
return 1;//1为颠倒顺序
return 0;
}
};
然后将cmp作为TreeSet的参数：
TreeSet set = new TreeSet(cmp);
之后就可以正常传入数据了。
总结
Set子接口有两大实现类：HashSet和TreeSet。 HashSet以哈希表作为存储结构，TreeSet以红黑树作为存储结构。 若想要以TreeSet类存储元素，存储的元素的类型需要实现Comparable接口，或者在定义时以Compare类作为参数。
新人一个，撰写文章时可能会有一些漏缺点和不足点，希望大家在评论区帮忙批评改正，各位多多海涵。
精彩内容
发表评论