Collection集合学习笔记
集合框架说明
-
首先,Java集合分为两个大类(都在java.util包下),一个是Collection接口(继承了Iterable接口,实现这个Iterable接口的对象允许使用foreach进行遍历,也就是说,所有的Collection集合对象都具有"foreach可遍历性"),另一个是Map(独立的接口)。Collection和Map是Java集合框架的根接口,这两个接口又包含了一些子接口或实现类。
-
Set、List和Map可以看做集合的三大类:
List集合是有序集合,集合中的元素可以重复,访问集合中的元素可以根据元素的索引来访问。
Set集合是无序集合,集合中的元素不可以重复,访问集合中的元素只能根据元素本身来访问(也是集合里元素不允许重复的原因)。
Map集合中保存Key-value对形式的元素,访问时只能根据每项元素的key来访问其value。 -
常用集合分类(长短表示继承关系)
Collection 接口的接口 对象的集合(单列集合)
├——-List 接口:元素按进入先后有序保存,可重复
│—————-├ LinkedList 接口实现类, 链表, 插入删除, 没有同步, 线程不安全
│—————-├ ArrayList 接口实现类, 数组, 随机访问, 没有同步, 线程不安全
│—————-└ Vector 接口实现类 数组, 同步, 线程安全
│ ———————-└ Stack 是Vector类的实现类
└——-Set 接口: 仅接收一次,无序不可重复,并做内部排序
├—————-└HashSet 使用hash表(数组)存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树,元素排好序Map 接口 键值对的集合 (双列集合)
├———Hashtable 接口实现类, 同步, 线程安全
├———HashMap 接口实现类 ,没有同步, 线程不安全-
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└———LinkedHashMap**
Collection接口中的常用方法
List接口
-
基本介绍
- 代表一个有序集合
- 允许有重复元素
- 可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素
2. 遍历方法
-
使用 foreach遍历集合
for (Integer i: list) {
System.out.print(i + " "); // 1 2 3 4 5
}
-
Iterator it = list.iterator();
while (it.hasNext()) {
Integer i = it.next();
System.out.print(i + " "); // 1 2 3 4 5
}
-
使用下标遍历集合
for (int i = 0; i < list.size(); i++) {
Integer j = list.get(i);
System.out.print(j + " "); // 1 2 3 4 5
}
List下的几个常用实现类
ArrayList
-
底层数据结构是数组,查询快,增删慢,线程不安全,效率高,可以存储重复元素
-
ArrayList实现了List的接口,实现了可变大小的数组,随机访问和遍历元素时,提供更好的性能。该类也是非同步的,在多线程的情况下不要使用。ArrayList 增长当前长度的50%,插入删除效率低。
-
方法见Collection
LinkedList
-
底层数据结构是链表,查询慢,增删快,线程不安全,效率高,可以存储重复元素
-
LinkedList其实也就是我们在数据结构中的链表,这种数据结构有这样的特性:
- 分配内存空间不是必须是连续的;
- 插入、删除操作很快,只要修改前后指针就OK了,时间复杂度为O(1);
- 访问比较慢,必须得从第一个元素开始遍历,时间复杂度为O(n)
-
方法见上图
Vector
- 底层数据结构是数组,查询快,增删慢,线程安全,效率低,可以存储重复元素
- Stack(因为是继承的Vector类,所以也能用List里的方法,但是按照栈先进后出的特点还提供了特别的方法(我猜的))
-
E push(E item) 把项压入堆栈顶部 E pop() 移除堆栈顶部的对象,并作为此函数的值返回该对象。 E peek() 查看堆栈顶部的对象,但不从堆栈中移除它。 boolean empty() 测试堆栈是否为空。 int search(Object o)返回对象在堆栈中的位置,以 1 为基数
Set接口
-
基本介绍
- Set集合类似于一个罐子,程序可以依次把多个对象“丢进”Set集合,而Set集合通常不能记住元素的添加顺序。
- 实际上Set就是Collection只是行为略有不同(Set不允许包含重复元素)。
- Set集合不允许包含相同的元素,如果试图把两个相同元素加入同一个Set集合中,则添加操作失败,add()方法返回false,且新元素不会被加入。
-
遍历方法(因为他无序,无法用下标来取得想要的值)
-
for增强循环
Set set = new HashSet();
for (String str : set) {
System.out.println(str);
} -
迭代器遍历
Iterator it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next);
} -
用的比较少(主要用于泛型的遍历)
比如:
Set set = new HashSet();
for (Object obj: set) {
if(obj instanceof Integer){ //若是Integer类型对象
int aa= (Integer)obj; //从包装类Integer 转为基本数据类型
}else if(obj instanceof String){ //若是String类型对象 转为String类型
String aa = (String)obj
}
}
-
Set下的几个常用实现类
HashSet
-
底层数据结构采用哈希表实现,元素无序且唯一,线程不安全,效率高,可以存储null元素,元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的,如果没有重写这两个方法,则无法保证元素的唯一性。
(注: 这两个方法是Object类下面的)
-
哈希表
一个元素为链表的数组,综合了数组与链表的优点。
HashSet具有以下特点:
-
不能保证元素的排列顺序,顺序可能与添加顺序不同,顺序也可能发生变化;
-
HashSet不是同步的;
-
集合元素值可以是null;
-
内部存储机制
-
实现唯一性的比较过程:存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值,然后和所存储的元素的hashCode值比较,如果hashCode不相等,则所存储的两个对象一定不相等,此时存储当前的新的hashCode值处的元素对象;如果hashCode相等,存储元素的对象还是不一定相等,此时会调用equals()方法判断两个对象的内容是否相等,如果内容相等,那么就是同一个对象,无需存储;如果比较的内容不相等,那么就是不同的对象,就该存储了,此时就要采用哈希的解决地址冲突算法,在当前hashCode值处类似一个新的链表, 在同一个hashCode值的后面存储存储不同的对象,这样就保证了元素的唯一性。
-
Set的实现类的集合对象中不能够有重复元素,HashSet也一样他是使用了一种标识来确定元素的不重复,HashSet用一种算法来保证HashSet中的元素是不重复的, HashSet采用哈希算法,底层用数组存储数据。默认初始化容量16,加载因子0.75。
-
Object类中的hashCode()的方法是所有子类都会继承这个方法,这个方法会用Hash算法算出一个Hash(哈希)码值返回,HashSet会用Hash码值去和数组长度取模, 模(这个模就是对象要存放在数组中的位置)相同时才会判断数组中的元素和要加入的对象的内容是否相同,如果不同才会添加进去。
Hash算法是一种散列算法。 -
判断流程
hs.add(o);
|
o.hashCode();
|
o%当前总容量 (0–15)
|
| 不发生冲突
是否发生冲突—————–直接存放
|
| 发生冲突
| 假(不相等)
o1.equals(o2)——————-找一个空位添加
|
| 是(相等)
不添加
-
-
代码实现及测试
- 存储类型没有重写equals()方法 和 hashCode()方法
public class Hero {
private String name;
private String nickname;
public Hero(String name, String nickname) {
this.name = name;
this.nickname = nickname;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getNickname() {
return nickname;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
@Override
public String toString() {
return "Hero{" +
"name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
public class TestHashSet {
public static void main(String[] args) {
Hero h1 = new Hero("宋江","及时雨");
Hero h2 = new Hero("卢俊义","玉麒麟");
Hero h3 = new Hero("吴用","智多星");
Hero h4 = new Hero("林冲","豹子头");
Hero h5 = new Hero("林冲","豹子头");
HashSet<Hero> set = new HashSet<>();
set.add(h1);
set.add(h2);
set.add(h3);
set.add(h4);
set.add(h5);
for (Hero hero : set) {
System.out.println(hero);
}
/*
Hero{name='卢俊义', nickname='玉麒麟'}
Hero{name='林冲', nickname='豹子头'}
Hero{name='林冲', nickname='豹子头'}
Hero{name='宋江', nickname='及时雨'}
Hero{name='吴用', nickname='智多星'}
可以看出这时set集合中的元素是可以重复的,因为Hero里没有重写equal和hashcode方法
*/
}
}
2. 存储类型重写equals()方法 和 hashCode()方法
//下面两个方法写在上面Hero类里
@Override
public int hashCode() {
return Objects.hash(name,nickname);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Hero hero = (Hero) obj;
return name == hero.name &&
Objects.equals(nickname, hero.nickname);
}
public class TestHashSet {
public static void main(String[] args) {
Hero h1 = new Hero("宋江","及时雨");
Hero h2 = new Hero("卢俊义","玉麒麟");
Hero h3 = new Hero("吴用","智多星");
Hero h4 = new Hero("林冲","豹子头");
Hero h5 = new Hero("林冲","豹子头");
HashSet<Hero> set = new HashSet<>();
set.add(h1);
set.add(h2);
set.add(h3);
set.add(h4);
set.add(h5);
for (Hero hero : set) {
System.out.println(hero);
}
/*
Hero{name='宋江', nickname='及时雨'}
Hero{name='卢俊义', nickname='玉麒麟'}
Hero{name='吴用', nickname='智多星'}
Hero{name='林冲', nickname='豹子头'}
可以看出这时set集合中的元素是b不可以重复的,因为Hero里重写了equal和hashcode方法
*/
}
}
TreeSet
-
底层数据结构采用红黑树来实现,元素唯一且已经排好序
-
唯一性同样需要重写hashCode和equals()方法,二叉树结构保证了元素的有序性。(注: 这两个方法是Object类下面的)
-
根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造),自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法,元素通过比较返回的int值来判断排序序列,返回0说明两个对象相同,不需要存储
-
比较器排序需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象,或者采用匿名内部类的方式new一个Comparator对象,重写里面的compare()方法;
-
两种排序方式
- 基本数据类型默认按升序排序
- 自定义排序(自然排序和比较器排序)
-
代码实现
-
自然排序:实现Comparable接口,并重写Compareto方法
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; } }
-
比较器排序:重写Comparator接口中的Compare方法
-
对基本数据类型进行比较器排序
o1:代表当前添加的数据 o2:代表集合中已经存在的数据 0: 表示 o1 == o2 -1(逆序输出): o1 < o2 1(正序输出): o1 > o2 1:o1 - o2(升序排列) -1:o2 - o1 (降序排列) 当compare()方法返回值大于0(为true)时,交换o1和o2 假设Comparator接收的两个元素原始顺序为:o1→o2 默认情况下升序:return o1>o2(假设为true)时,交换为:o2→o1(o1大,在后,即升序) 改写为降序时:return o2>o1(假设为true)时,交换为:o2→o1(o1小,在后,即降序) Comparator<Integer> comp = new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { System.out.println(o1+"--"+o2); return o2 -o1; //输出53 33 10,降序排序 // return 0; //只输出一个元素:33 // return -1; //输出53 10 33,倒序输出 // return 1; //输出33 10 55 } };
-
对引用数据类型进行比较器排序
#1.单独创建一个比较类,这里以MyComparator为例,并且要让其继承Comparator接口 public class MyComparator implements Comparator<Student> { @Override #2.重写Comparator接口中的Compare方法 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; } } #3、指定自己写的比较类 TreeSet<Student> ts=new TreeSet<Student>(new MyComparator());
-
-
List和Set总结
-
List,Set都是继承自Collection接口,Map则不是
-
List特点:元素有放入顺序,元素可重复
-
**Set特点:**元素无放入顺序,元素不可重复,重复元素会覆盖掉,(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的,加入Set 的Object必须定义equals()方法 ,另外list支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。)
-
Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变。 -
ArrayList与LinkedList的区别和适用场景
-
-
Arraylist:
优点:ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
缺点:因为地址连续, ArrayList要移动数据,所以插入和删除操作效率比较低。 -
LinkedList:
优点:LinkedList基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址,对于新增和删除操作add和remove,LinedList比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景
缺点:因为LinkedList要移动指针,所以查询操作性能比较低。
适用场景分析:
当需要对数据进行经常访问的情况下选用ArrayList,当需要对数据进行多次增加删除修改时采用LinkedList。 -
区别:
-
ArrayList和Vector都是用数组实现的,主要有这么三个区别:
(1)Vector是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果。而ArrayList不是,这个可以从源码中看出,Vector类中的方法很多有synchronized进行修饰,这样就导致了Vector在效率上无法与ArrayList相比;
(2)两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。
(3)Vector可以设置增长因子,而ArrayList不可以。
(4)Vector是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。 -
适用场景分析:
(1)Vector是线程同步的,所以它也是线程安全的,而ArrayList是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用ArrayList效率比较高。
(2)如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用Vector有一定的优势。 -
HashSet和TreeSet的区别和适用场景
(1)TreeSet 是二叉树(红黑树的树据结构)实现的,Treeset中的数据是自动排好序的,不允许放入null值
(2)HashSet 是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,两者中的值都不能重复,就如数据库中唯一约束
(3)HashSet要求放入的对象必须实现HashCode()方法,放入的对象,是以hashcode码作为标识的,而具有相同内容的String对象,hashcode是一样,所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例(4)适用场景分析:HashSet是基于Hash算法实现的,其性能通常都优于TreeSet。为快速查找而设计的Set,我们通常都应该使用HashSet,在我们需要排序的功能时,我们才使用TreeSet。
-
Map接口中的常用方法
-
基本介绍
- Map用于保存具有映射关系的数据,Map里保存着两组数据:key和value,它们都可以使任何引用类型的数据,但key不能重复。所以通过指定的key就可以取出对应的value。
- Map接口有四个比较重要的实现类,分别是HashMap、LinkedHashMap、TreeMap和HashTable。
- TreeMap是有序的,HashMap和HashTable是无序的。
- Hashtable的方法是同步的,HashMap的方法不是同步的。这是两者最主要的区别。
- Map 没有继承 Collection 接口, Map 提供 key 到 value 的映射,你可以通过“键”查找“值”。
- 一个 Map 中不能包含相同的 key ,每个 key 只能映射一个 value 。
- Map 接口提供 3 种集合的视图, Map 的内容可以被当作一组 key 集合,一组 value 集合,或者一组 key-value 映射。
-
常用方法
Queue接口
-
基本介绍
-
Queue接口与List、Set同一级别,都是继承了Collection接口。LinkedList实现了Queue接口。我们平时使用的一些常见队列都是非阻塞队列,比如PriorityQueue、LinkedList(LinkedList是双向链表,它实现了Dequeue接口)
-
阻塞队列与普通队列的区别在于,当队列是空的时,从队列中获取元素的操作将会被阻塞,或者当队列是满时,往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞,直到其他的线程往空的队列插入新的元素。同样,试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞,直到其他的线程使队列重新变得空闲起来,如从队列中移除一个或者多个元素,或者完全清空队列。
-
使用非阻塞队列的时候有一个很大问题就是:它不会对当前线程产生阻塞,那么在面对类似消费者-生产者的模型时,就必须额外地实现同步策略以及线程间唤醒策略,这个实现起来就非常麻烦。但是有了阻塞队列就不一样了,它会对当前线程产生阻塞,比如一个线程从一个空的阻塞队列中取元素,此时线程会被阻塞直到阻塞队列中有了元素。当队列中有元素后,被阻塞的线程会自动被唤醒(不需要我们编写代码去唤醒)。这样提供了极大的方便性。
-
-
非阻塞队列中的几个主要方法(主要是对LinkedList的使用比较多)
- add(E e) : 将元素e插入到队列末尾,如果插入成功,则返回true;如果插入失败(即队列已满),则会抛出异常;
- remove() :移除队首元素,若移除成功,则返回true;如果移除失败(队列为空),则会抛出异常;
- offer(E e) :将元素e插入到队列末尾,如果插入成功,则返回true;如果插入失败(即队列已满),则返回false;
- poll() :移除并获取队首元素,若成功,则返回队首元素;否则返回null;
- peek() :获取队首元素,若成功,则返回队首元素;否则返回null
对于非阻塞队列,一般情况下建议使用
offer、poll和peek
三个方法,不建议使用add和remove方法。因为使用offer、poll和peek三个方法可以通过返回值判断操作成功与否,而使用add和remove方法却不能达到这样的效果。注意,非阻塞队列中的方法都没有进行同步措施。