List 有序的 可重复
Set 无序 不可重复的
Map 映射关系的集合
一． List
1.1ArrayList
<u>List</u> list= new ArrayList<>();//形成多态
底层： 数组
特点：定长 线程不安全
扩容：每次扩容到原来的1.5倍
位于 java.util 包中
如果 List list = new ArrayList();
则默认创建了一个长度为0 的数组。
重点： 如何遍历ArrayList ？
1） 普通的for循环：
for(<u>int</u> i = 0;i<list.size();i++) {
//从集合中将数据取出
String message = list.get(i);
System.out.println(message);
}
2） 增强的for循环：
for (String value : list) {
System.out.println(value);
}
3） 通过集合对象获得迭代器对象
Iterator<String> iterator= list.iterator();
**while**(iterator.hasNext()) {
//取出元素
System.out.println(iterator.next());
}
注意****：
ArrayList list = new ArrauyList(); 在****java 1.6 初始化为长度为****10****的数组****，****在****1.8****之后长度为****0；
如何需要将****ArrayList 转换成线程安全的集合****：
** 1.Collections**
List<String> list = new ArrayList<>();
list = Collections.synchronizedList(list);
** 2.juc**
并发容器**** CopyOnWriteArrayList
1.2vector
底层：数组
特点：定长 线程安全 比较老旧 不建议使用
扩容：每次扩大两倍
Api与ArrayList相同
遍历：与ArrayList相同
如果我们创建一个vector 集合如下
Vector vector = new Vector()；
则默认创建了一个长度为10的数组。
如果指定了参数，则创建（原来长度+参数）长度的数组。
1.3Linkedlist
底层：链表 是一个双向链表
特点：线程不安全 不定长
Api与ArrayList相同
遍历：与ArrayList相同
Add（e） 指的是往链表的尾部添加节点。
链表：
[图片上传失败...(image-92c29a-1585982687109)]
LinkedList get方法的原理 *******
类似于折半查找。先找到中间值
如果查找元素比中间值大，则从右边从后往前遍历
如果查找元素比中间值小，则从左边从头往后遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
1.4 List总结
1）使用的时候api相同
ArrayList 数组
LinkedList 链表
Vector 数组
2）数组：ArrayList Vector
数组定长的
数组的、存放数据 单一类型的
查找 修改 比较快
添加 删除 慢的
链表：LinkedList
查找 修改 慢
添加 删除 快
- 集合可以储存多种类型 但是不建议 容易出现类型转换出错
集合不需要关心扩容问题。
4） 不同点
ArrayList 底层数组 线程不安全 查找、修改快
Vector 底层数组 线程安全 查找、修改快 过时
LinkedList 底层链表 线程不安全 增加、删除比较快
二． Set
特点：无序 不可重复
2.1 HashSet
底层：HashMap HashMap 底层 用的 哈希表
Set集合如何进行迭代？
Set<> set = new HashSet<>();
- foreach
for(String value : set){
system.out.println(value);
}
- 获得迭代器
Iterator<String> iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
注意：
1.在Set中存放字符串 根据字符串的内容判重
2.在Set中存放对象（Student） 根据什么判重？
如何指定判重条件？
Name相同 认为是一个学生
Name id相同
Id 相同
重写 Student类中的 HashCode 和 equals 方法
使用eclipes 快捷方法 重写HashCode 和 equals 方法
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
- HashSet 判重使用的HashCode 和 equals方法*******
哈希表： 又称 散列表 -> 数组＋链表
根据HashCode计算方法：计算数组下标
Equals 方法 判断是否具有重复元素
HashCode 的作用是快速定位数据
equals方法****的作用是比较链表上的元素是否相同
4.哈希表：又称散列表 -> 数组加链表
[图片上传失败...(image-c604ba-1585982687108)]
2.2 TreeSet
底层：TreeMap TreeMap底层用的红黑树。
使用
对于简单类型 默认使用字典排序 或者 自然排序
对于复杂类型 不能直接进行迭代 需要有一下两种方法中的一种：
1） 实体类 实现 接口Comparable
public class Student implement Comparable<Student>{}
在Student 类 里面 重写compareTo方法
升序
@Override
public int compareTo(Student o){
if(this.id > o.getId){
return 1;
}
If(this,id < o.getId ){
Return -1;
}
Return 0;
降序
@Override
public int compareTo(Student o){
if(this.id > o.getId){
return -1;
}
If(this,id < o.getId ){
Return 1;
}
Return 0;
2） 自定义比较器
Set<E> set = new TreeSet(comparator); //把比较器对象传进来
Comparator<E> comparator = new Comparator<E>(){ //匿名内部类
降序
@Override
If(o1.getId > o2.getId){
Return -1;
}else if(o1.getId < o2.getId){
Return 1
}
Return 0;
}
三． Map
Map 具有映射关系的集合 key-value 语文-99
3.1 HashMap
底层：哈希表
注意：
Key-value 允许使用null值。
Map只能根据Key获得Value，不能根据Value获得Key。
Map中 Key不可重复 而 Value 可重复。
HashMap的迭代：
- 把key放入set集合里
Set<E> keySet = map.keySet(); //E 存放Key值 对应的类型。
for(String key : keyset){
sysout.out.println(key + “ :” +map.get(key));
}
- 把 Key 和 Value组成一个对象 放到Entry 对象里。
Set<Entry<K,V>> set = map.entrySet();
for(Entry<String, Double> entry: set) {
System.out.println(entry.getKey() +" :"+ entry.getValue());
}
3.2 TreeMap
底层：红黑树
特点：可排序（Key值 可排序）
如果Key值 是 简单类型 基于字典排序
如果Key值 是 复杂类型 基于自定义的排序规则
排序规则同TreeSet。另外可用三目运算符。
1>实体类 实现 接口Comparable
1.public class Student implement Comparable<Student>{}
2.在Student 类 里面 重写compareTo方法
@Override 升序 （如果1 在前面 就是升序）
Public int compareTo(Student o){
return this.getAge > o.getAge ? 1 : ( this.getAge < o.getAge)?-1:0;
}
2>创建自定义比较器 Comparator 使用匿名内部类的形式 重写compare方法
TreeMap<Student, Integer> map= new TreeMap<>(new Comparator<Student>() {
@Override
public intcompare(Student o1, Student o2) {
// TODO Auto-generated method stub
return o1.getAge() > o2.getAge() ? 1 : (o1.getAge() < o2.getAge())?-1:0;
}
});
TreeMap的迭代： ****同HashMap
- 把key放入set集合里
Set<E> keySet = map.keySet(); //E 存放Key值 对应的类型。
for(String key : keyset){
sysout.out.println(key + “ :” +map.get(key));
}
- 把 Key 和 Value组成一个对象 放到Entry 对象里。
Set<Entry<K,V>> set = map.entrySet();
for(Entry<String, Double> entry: set) {
System.out.println(entry.getKey() +" :"+ entry.getValue());
}
3.3Hashtable
A****pi的使用与HashMap相同。
特点：1.是线程安全的类 同步集合
- key – value 不允许使用 null值。
3.4Map集合的补充
1.关于Map 集合的扩容问题
HashMap map = new HashMap();
默认创建的数组的长度为16， 加载因子为0.75 。当添加的数据数 到达 16*0.75 = 12时
Map集合将在底层进行扩容 扩容到原来的两倍
- 在 JDK8 中 HashMap的底层不再单纯的是哈希表了
底层： 哈希表 + 红黑树
如果哈希表中 链表的长度 >= 7 则转换为红黑树。
