复习:
Queue -> 队列:先进先出
Deque -> 双端队列/栈
LinkedList(C)
双端队列:
offer()
poll()
peek()
栈:先进后出
push()
pop()
Set(I) - 无序且唯一
|- HashSet(C)
插入过程:
1.通过hashCode()定位
2.判断该位置上是否存在元素
3.如果不存在,则直接存入
4.如果存在,使用equals()判断对象是否相等
5.如果不相等,则直接存入链表末尾
6.如果相等,则进行覆盖
|- TreeSet(C)
满二叉树
完全二叉树
排序二叉树
平衡二叉树
二叉树的遍历
先序遍历
中序遍历
后序遍历
____________________________________________
自然排序(比较器)和自定义排序(指定比较器):
1.自然排序 - Comparable(I)
1).使用步骤
a.在实体类中实现Comparable接口
b.重写Comparable中的compareTo()
2).比较规则:
a. this 和 obj必须是同一种类型
b. this 比 obj 小, 返回负数
this 比 obj 大, 返回正数
this 和 obj 一样大, 返回0,则不存入
c.正序和倒序
正序: this在前,obj在后 -> 前比后
倒序: obj在前,this在后 -> 后比前
2.自定义排序 - Comparator(I)
1).使用步骤:
a.使用匿名内部类方式实现Comparator接口
b.重写Comparator接口中的compare()
2).比较规则
a.比较的是传进来的两个对象
b.compare()返回0的时候,表示所有对象都一样,默认按照原本顺序排序.
c.正序和倒序
正序: 前比后
倒序: 后比前
java当中的排序方法:
1.数组
Arrays.sort(arr) -> 自然排序
Arrays.sort(arr,new Comparator) -> 自定义排序
2.List
Collections.sort(list) ->自然排序
Collections.sort(list,new Comparator) ->自定义排序
存在ArrayList中的sort,没有重载
list.sort(new Comparator) ->自定义排序
3.Set
new TreeSet() -> 自然排序
new TreeSet(new Comparator) -> 自定义排序
4.Map
new TreeMap() ->自然排序
new TreeMap(new Comparator)-> 自定义排序
____________________________________________
Map(I):
1.特点:
1).Map集合是一个双列集合,是以key-value的形式表示.
2)key和value都可以使用泛型,也就意味着可以使用引用数据类型(自定义类)
3).key值都不允许有重复值
4).value值允许有多个重复值
5).如果key值完全一致,则value值会被覆盖
6).因为key是唯一的,可以通过key找到value值
2.Map接口的结构:
Map(I)
|- HashMap(C)
|- LinkedHashMap(C)
|- HashTable(C)
|- ConcurrentHashMap(C)
|- SortedMap(I)
|- TreeMap(C)
____________________________________________
HashMap(C):
1.底层实现: 哈希表(散列表)
2.底层数据结构:
JDK1.7: 数组 + 双向链表
JDK1.8: 数组 + 双向链表 + 红黑树
3.特点:
就是Map接口的特点
4.HashMap的存储过程:
a.计算key的hashCode值,确定位置
b.如果位置上有元素,则使用equals()和该位置上的所有元素比较
c.如果元素一致,会进行覆盖
d.如果元素不一致,则直接存入链表末尾
5.初始空间大小
a.默认初始容量:16
b.加载因子: 0.75 -> 容量达到百分之75的时候进行扩容
b.如果元素太少就进行扩容,会造成空间的浪费
c.如果元素太多进行扩容,则会造成效率低下
6.常用API
put()
get()
remove()
boolean containsKey(Object key)
boolean containsKey(Object key)
boolean isEmpty()
int size()
void putAll(Map<? extends K,? extends V> m)
7.Map的遍历方式
1)获取所有的key,并且得到对应的Set集合类型
map.keySet()
2)获取所有的value,并且得到对应的List集合类型
map.values()
3)获取所有的键值对entry,并且得到对应的Set集合类型
注意:
a.在set集合中只能存放一种泛型,所以键值对(entry)也是一个整体泛型类型
b.Entry是属于Map的内部接口,内部接口的使用方式和内部类一样
c.Entry的结构
获取键:
getKey()
获取值:
geyValue()
8.LinkedHashMap(C)
1)底层数据结构:数组+链表+双向链表
2)特点:
a.按照插入顺序进行排列
9.TreeMap(C)
1)底层数据结构:红黑树
2)作用:
a.对Map集合进行排序
10.Hashtable(C)
1)底层数据结构: 数组 + 链表
2)和HashMap的区别
a.父类的不同
b.线程安全
c.版本问题
d.扩容问题
e.是否可以存在null值
11.ConcurrentHashMap(C)
1)底层数据结构:
JDK1.7: 数组 + 链表
Segment数组 + hashEntry数组 + hashEntry链表
JDK1.8: 数组 + 链表|红黑树
CAS + synchronized(同步锁)
CAS全称: Compare And Swap - 比较并交换
三个数据值:
内存值V 当前值A 修改的新值B
情况1:
内存值V 和 当前值A 比较结果相同,将修改的新值B替换内存值V的值
情况2:
内存值V 和 当前值A 比较结果不相同,要么重试,要么就放弃更新
CAS的目的: 把内存值V 和 当前值A进行比较
synchronized锁: 每一次会让一个线程操作共享的数据,而CAS相当于是没有加锁,多个线程就都可以操作共享的数据.
在实际去修改的时候才会去判断能否修改成功.
12.JDK1.9的新特性 - of()
1).List接口,Set接口,Map接口中都新增了一个静态方法,可以给集合做一次性添加多个元素
2)注意:
a. of()只能适用于List/Set/Map集合,不指定到实现类中
b. of()的返回值是一个不可改变的集合,否则都会抛出UnsupportedOperationException - 不支持的异常
c. Set/Map集合在调用of()的时候,不能有重复值,否则就会抛出IllegalArgumentException - 非法参数异常
______________________________________________
集合内容回顾:
Collection的父接口 Iterable接口,可迭代的接口
Iterator:迭代器
hasNext()
Next()
remove()
简易版迭代器: foreach
Collection(I)
|- List(I) - 有序,并且可以有重复值
|- ArrayList(C)
数据结构:顺序结构
特点: 查询快,增删慢
|- LinkedList(C)
数据结构:链式结构
特点: 查询慢,增删快
|- Vector(C)
数据结构:顺序结构
特点: 查询快,增删慢
带有锁
|- Stack(C) - 作为栈实现
|- Set(I) - 无序且唯一
|- HashSet(C)
数据结构:hash表(数组 + 链表)
|- SortedSet(I)
|- TreeSet(C)
数据结构:二叉树
|- Queue(I) - 先进先出
|-Deque(I) - 双端队列/栈
|- LinkedList(C)
Map(I)
|- HashMap(C) - 普通存储数据
数据结构:哈希表(散列表)|红黑树
默认初始容量:16
扩容因子:0.75
|-LinkedHashMap(C) - 存储有插入顺序
数据结构: 哈希表+双向链表
|-SortedMap(I)
|-TreeMap(C) - 对Map进行排序
|-Hashtable(C)
数据结构:哈希表
|-ConcurrentHashMap(C) - 并发(线程)
自然排序:Comparable(I)
重写compareTo() -> 比较 this 和 obj
this 比 obj 小
this 比 obj 大
this 和 obj 相同
this在前,obj在后 正序
obj在前,this在后 倒序
自定义排序: Comparator(I)
重写compare() -> 比较 o1 和 o2
正序: 前比后
倒序: 后比前
排序方式:
数组
Arrays.sort()
List
Collections.sort()
Set
new TreeSet()
Map
new TreeMap()