一、集合大纲
1. 集合和数组的区别
2.Collection 集合的方法
3. 常用集合的分类
Collection 接口的接口 对象的集合(单列集合)
├——-List 接口:元素按进入先后有序保存,可重复
│—————-├ LinkedList 接口实现类, 链表, 插入删除, 没有同步, 线程不安全
│—————-├ ArrayList 接口实现类, 数组, 随机访问, 没有同步, 线程不安全
│—————-└ Vector 接口实现类 数组, 同步, 线程安全
│ ———————-└ Stack 是 Vector 类的实现类
└——-Set 接口: 仅接收一次,不可重复,并做内部排序
├—————-└HashSet 使用 hash 表(数组)存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树,元素排好序
Map 接口 键值对的集合 (双列集合)
├———Hashtable 接口实现类, 同步, 线程安全
├———HashMap 接口实现类 ,没有同步, 线程不安全 -
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的 key 进行排序
└———IdentifyHashMap
二、List 和 Set 集合详解
2.1 list 和 set 的区别
2.2 List特性详解
(1)ArrayList:底层数据结构是数组,查询快,增删慢,线程不安全,效率高,可以存储重复元素
- ArrayList底层数组的默认长度是10个,每次的扩容是原来长度的1.5倍。
(2)Vector: 底层数据结构是数组,查询快,增删慢,线程安全,效率低,可以存储重复元素
(3)LinkedList 底层数据结构是链表,查询慢,增删快,线程不安全,效率高,可以存储重复元素
- LinkedList底层实现原理是双向链表。
2.3 Set特性
- Set下有HashSet,LinkedHashSet,TreeSet。
- Set 具有与 Collection 完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的 List。实际上 Set 就是 Collection, 只 是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)
- Set 不保存重复的元素。加入 Set 的元素必须定义 equals() 方法以确保对象的唯一性。Set 与 Collection 有完全一样的接口。
- Set 接口不保证元素的存取有序。
2.3.1 HashSet
HashSet:底层数据结构是哈希表。(保证唯一)
如何来保证元素唯一性?
依赖两个方法:hashCode()和equals()。
HashSet底层原理:
HashSet的底层数据结构时哈希表,在存储元素时,会进行以下几步:
① HashSet底层会自动多次调用hashCode()方法,以尽量减少出现哈希碰撞的几率,最终得出一个哈希值,并根据这个哈希值判断对象在数组中的存储位置。
② 得到对象在数组中的存储位置后,先判断该位置是否为空,如果为空,就直接存储;如果不为空,再遍历该位置下的链表并使用equals()方法判断二者是否相等,如果不相等,就将对象存到链表的最后一个位置(jdk1.8以后采用尾插法);如果相等,就将之前的对象覆盖。
③ JDK1.8以后,哈希表又多了一个红黑树结构。即哈希表
在JDK1.8以后是由 数组+链表+红黑树
组成。其实现原理大致如下:
- 在数组容量 >= 64的前提下,如果某个数组索引下的链表长度大于等于 8 ,那么这个链表就转换为红黑树。
- 当红黑树的长度小于等于 6 时,红黑树就会转为链表。(数组只能扩容,不能减少长度)
① 哈希表的数据结构
HashSet集合不具备任何功能,内部调用了另一个集合对象:HashMap。而HashMap是由哈希表构成的,因此HashSet的底层就是哈希表。
-
HashSet的无参构造方法
public HashSet() { map = new HashMap<>(); }
两个知识点:
- 哈希值的结果不知道是怎么计算的,调用toString()方法的时候,返回的十六进制数和哈希值是一样的。即对象.toString()返回的值:
XXX@1b6d3586
叫哈希值 (根本和内存地址是无关的)。- 两个对象的哈希值相同,不要求equals一定返回true.。两个对象的equals返回true,两个对象的哈希值必须一致。
1、哈希表是由 数组 + 单链表 组成的。jdk1.8以后哈希表是由 数组+链表+红黑树 组成的。
2、哈希表的底层数组长度默认是16个,扩容后为原来长度的2倍
3、哈希表的加载因子默认是0.75F,即数组中存储元素的个数达到长度的75%,哈希表会自动扩容。
几个名词:
- 哈希表的实例:数组
- '桶':相同数组索引下的链表
- 哈希碰撞:哈希值相同
② 哈希表存储对象的过程
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
//存储对象
set.add("abc");
set.add("bbc");
set.add(new String("abc"));
set.add("通话");
set.add("重地");
System.out.println("set = " + set);
}
2.3.2 LinkedHashSet
LinkedHashSet:底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
1.由链表保证元素存取有序
2.由哈希表保证元素唯一
2.3.3 TreeSet
TreeSet 底层数据结构采用红黑树来实现。元素唯一且有序。
1. 唯一性同样需要重写 hashCode 和 equals() 方法。
2. 红黑树结构保证了元素的有序性。根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造)。
- 自然排序要求元素必须实现 Compareable 接口,并重写里面的 compareTo() 方法,元素通过比较返回的 int 值来判断排序序列,返回 0 说明两个对象相同,不需要存储。
- 比较器排序需要在 TreeSet 初始化是时候传入一个实现 Comparator 接口的比较器对象,或者采用匿名内部类的方式 new 一个 Comparator 对象,重写里面的 compare() 方法。
2.4 何时使用List和Set
- 如果你知道用集合,就用ArrayList。
- 如果你知道是Collection集合,但是不知道使用谁,就用ArrayList。
- 如果你知道是Set,但是不知道是哪个Set,就用HashSet。
三、Map 详解
3.1 Map集合体系结构
Map 接口 键值对的集合 (双列集合)
├———Hashtable 接口实现类, 同步, 线程安全
├———HashMap 接口实现类 ,没有同步, 线程不安全 -
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的 key 进行排序
└———IdentifyHashMap
Map 用于保存具有映射关系的数据,Map 里保存着两组数据:key 和 value,它们都可以使任何引用类型的数据,但 key 不能重复。所以通过指定的 key 就可以取出对应的 value。
请注意!!!, Map 没有继承 Collection 接口, Map 提供 key 到 value 的映射,你可以通过 “键” 查找“值”。一个 Map 中不能包含相同的 key ,每个 key 只能映射一个 value 。 Map 接口提供 3 种集合的视图, Map 的内容可以被当作一组 key 集合,一组 value 集合,或者一组 key-value 映射。
3.2 Map常用方法
3.3 Map的三个实现类
Map接口有三个比较重要的实现类,分别是HashMap、TreeMap和HashTable。
- TreeMap是有序的,HashMap和HashTable是无序的。
- Hashtable的方法是同步的,HashMap的方法不是同步的。这是两者最主要的区别。
这就意味着:
-
Hashtable是线程安全的,HashMap不是线程安全的。
-
HashMap效率较高,Hashtable效率较低。
如果对同步性或与遗留代码的兼容性没有任何要求,建议使用HashMap。 查看Hashtable的源代码就可以发现,除构造函数外,Hashtable的所有 public 方法声明中都有 synchronized关键字,而HashMap的源码中则没有。
-
Hashtable不允许null值,HashMap允许null值(key和value都允许)
-
父类不同:Hashtable的父类是Dictionary,HashMap的父类是AbstractMap
3.4 TreeMap常用方法
3.5 Map 的其它类
IdentityHashMap 和 HashMap 的具体区别,IdentityHashMap 使用 ==
判断两个 key 是否相等,而 HashMap 使用的是 equals 方法比较 key 值。有什么区别呢?
对于 ==
,如果作用于基本数据类型的变量,则直接比较其存储的 “值” 是否相等; 如果作用于引用类型的变量,则比较的是所指向的对象的地址。
对于 equals 方法,注意:equals 方法不能作用于基本数据类型的变量
如果没有对 equals 方法进行重写,则比较的是引用类型的变量所指向的对象的地址;
诸如 String、Date 等类对 equals 方法进行了重写的话,比较的是所指向的对象的内容。
四、重点问题分析
4.1 TreeSet, LinkedHashSet and HashSet 的区别
4.1.1 介绍
- TreeSet, LinkedHashSet 和 HashSet 在java中都是实现Set的数据结构
-
TreeSet的主要功能用于排序
-
LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
-
HashSet只是通用的存储数据的集合
4.1.2 相同点
- 元素唯一:因为三者都实现Set接口,所以三者都不包含重复元素
- 线程不安全:三者都不是线程安全的,如果要使用线程安全可以Collections.synchronizedSet()
4.1.3 不同点
- 性能和速度:HashSet插入数据最快,其次LinkHashSet,最慢的是TreeSet因为内部实现排序
- 有序性:HashSet不保证有序,LinkHashSet保证FIFO即按插入顺序排序,TreeSet安装内部实现排序,也可以自定义排序规则
- null:
HashSet
和LinkHashSet
允许存在null数据,但是TreeSet中插入null数据时会报NullPointerException
4.1.4 代码比较
public static void main(String args[]) {
HashSet<String> hashSet = new HashSet<>();
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
TreeSet<String> treeSet = new TreeSet<>();
for (String data : Arrays.asList("B", "E", "D", "C", "A")) {
hashSet.add(data);
linkedHashSet.add(data);
treeSet.add(data);
}
//不保证有序
System.out.println("Ordering in HashSet :" + hashSet);
//FIFO保证安装插入顺序排序
System.out.println("Order of element in LinkedHashSet :" + linkedHashSet);
//内部实现排序
System.out.println("Order of objects in TreeSet :" + treeSet);
}
运行结果:
Ordering in HashSet :[A, B, C, D, E] (无顺序)
Order of element in LinkedHashSet :[B, E, D, C, A] (FIFO插入有序)
Order of objects in TreeSet :[A, B, C, D, E] (排序)
4.2 TreeSet的两种排序方式比较
4.2.1 基本数据类型
由于TreeSet可以实现对元素按照某种规则进行排序,例如下面的例子
public class MyClass {
public static void main(String[] args) {
// 创建集合对象
// 自然顺序进行排序
TreeSet<Integer> ts = new TreeSet<Integer>();
// 创建元素并添加
// 20,18,23,22,17,24,19,18,24
ts.add(20);
ts.add(18);
ts.add(23);
ts.add(22);
ts.add(17);
ts.add(24);
ts.add(19);
ts.add(18);
ts.add(24);
// 遍历
for (Integer i : ts) {
System.out.println(i);
}
}
}
运行结果:
17
18
19
20
22
23
24
4.2.2 引用数据类型
测试类:
public class MyClass {
public static void main(String[] args) {
TreeSet<Student> ts=new TreeSet<Student>();
//创建元素对象
Student s1=new Student("zhangsan",20);
Student s2=new Student("lis",22);
Student s3=new Student("wangwu",24);
Student s4=new Student("chenliu",26);
Student s5=new Student("zhangsan",22);
Student s6=new Student("qianqi",24);
//将元素对象添加到集合对象中
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
ts.add(s6);
//遍历
for(Student s:ts){
System.out.println(s.getName()+"-----------"+s.getAge());
}
}
}
Student.java:
public class Student {
private String name;
private int age;
public Student() {
super();
// TODO Auto-generated constructor stub
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
结果报错:
原因分析:
由于不知道该安照那一中排序方式排序,所以会报错。
解决方法:
1.自然排序
2.比较器排序
1. 自然排序
自然排序要进行一下操作:
-
Student类中实现 Comparable接口
-
.重写Comparable接口中的Compareto方法
this:后来的对象
o:先来的对象
compareTo(T o) 比较此对象与指定对象的顺序。
this - o:升序排序
o - this:降序排序
public class Student implements Comparable<Student>{
private String name;
private int age;
public Student() {
super();
// TODO Auto-generated constructor stub
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Student s) {
//return -1; //-1表示放在红黑树的左边,即逆序输出
//return 1; //1表示放在红黑树的右边,即顺序输出
//return o; //表示元素相同,仅存放第一个元素
//主要条件 姓名的长度,如果姓名长度小的就放在左子树,否则放在右子树
int num=this.name.length()-s.name.length();
//姓名的长度相同,不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前,则比较结果为一个负整数。
//如果按字典顺序此 String 对象位于参数字符串之后,则比较结果为一个正整数。
//如果这两个字符串相等,则结果为 0
int num1=num==0?this.name.compareTo(s.name):num;
//姓名的长度和内容相同,不代表年龄相同,所以还要判断年龄
int num2=num1==0?this.age-s.age:num1;
return num2;
}
}
运行结果:
lis-----------22
qianqi-----------24
wangwu-----------24
chenliu-----------26
zhangsan-----------20
zhangsan-----------22
2.比较器排序
比较器排序步骤:
- 单独创建一个比较类,这里以MyComparator为例,并且要让其继承Comparator接口。
- 重写Comparator接口中的Compare方法。
compare(T o1,T o2) 比较用来排序的两个参数。
o1 - o2:升序排序
o2 - o1:降序排序
o1:后来的对象
o2:先来的对象
- 在主类中使用下面的 构造方法
TreeSet(Comparator<? superE> comparator) 构造一个新的空 TreeSet,它根据指定比较器进行排序。
测试类:
public class MyClass {
public static void main(String[] args) {
//创建集合对象
//TreeSet(Comparator<? super E> comparator) 构造一个新的空 TreeSet,它根据指定比较器进行排序。
TreeSet<Student> ts=new TreeSet<Student>(new MyComparator());
//创建元素对象
Student s1=new Student("zhangsan",20);
Student s2=new Student("lis",22);
Student s3=new Student("wangwu",24);
Student s4=new Student("chenliu",26);
Student s5=new Student("zhangsan",22);
Student s6=new Student("qianqi",24);
//将元素对象添加到集合对象中
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
ts.add(s6);
//遍历
for(Student s:ts){
System.out.println(s.getName()+"-----------"+s.getAge());
}
}
}
Student.java:
public class Student {
private String name;
private int age;
public Student() {
super();
// TODO Auto-generated constructor stub
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
MyComparator类:
public class MyComparator implements Comparator<Student> {
@Override
public int compare(Student s1,Student s2) {
// 姓名长度
int num = s1.getName().length() - s2.getName().length();
// 姓名内容
int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
// 年龄
int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
return num3;
}
}
运行结果:
lis-----------22
qianqi-----------24
wangwu-----------24
chenliu-----------26
zhangsan-----------20
zhangsan-----------22
参考文章: