day03 数据结构 List/Set集合 Collections集合工具类
一数据结构
栈的特点: 先进后出
栈内存 (main方法先进栈调用, main方法中的其他方法都调用完毕后, main才能出栈)
队列的特点: 先进先出 队列的适用场景: 秒杀, 抢购 在线售票 处理高并发场景
数组的特点: 查询快: 增删慢:
链表的特点: 查询慢: 增删快:
红黑树: 是一种 平衡 二叉 查找 树
哈希表 (也就是: 数组 + 链表或红黑树 + 链表)
元素存储过程中就完成了大小排序 查询比链表快, 增删比数组快 (数组和链表的折中)
二集合 List 包含1 ArrayList, 2LinkedList, 3 Vector(了解)
\
Collection(集合)
/
set包含 1HashSet, 子类 LinkedHashSet 2 TreeSet
(1) List集合体系的特点:
1. 元素存取有序 (存入和取出元素的顺序一致) 321->321 排序: 从小到大
2. 元素可以重复 3. 有索引
List集合方法
1 list.add(3,"神") 指定位置添加指定元素
2 remove(3) 移除指定位置的元素,返回被移除的元素
3 list,set(4,"a") 指定元素替换指定位置的元素,返回更新前的元素
4 list.get list.get(length+1)容易越界异常
ArrayList底层的数据结构: 数组
LinkedList底层的数据结构: 链表
Vector底层的数据结构: 数组
LinkedList的方法
void addFirst(E e): 将指定元素插入此列表的开头
void addLast(E e): 将指定元素添加到此列表的结尾
void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
E getFirst(): 返回此列表的第一个元素
E getLast(): 返回此列表的最后一个元素
E removeFirst(): 移除并返回此列表的第一个元素
E removeLast(): 移除并返回此列表的最后一个元素
E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
(2) Set集合体系特点: 1. 元素不可重复 2. 没有索引
HashSet特点: 1. 元素不可重复 2. 没有索引
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用 哈希表 结构. (查询快) 哈希表 = 数组 + 链表或红黑树
大的数量会出现无序,小数量打印时是倒叙的
HashSet原理: 哈希值 一个十进制数值 模拟的逻辑地址,不是物理地址
自定义类时要重写下面的两个方法,有快捷键
hashCode()方法: 用于将对象计算为一个哈希值, 便于根据哈希值比较对象是否"相等"
如果哈希值相同, 则可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较
LinkedHashSet特点: 1. 元素存取有序 (存入和取出顺序一致)
2. 元素不可重复 3. 没有索引
底层采用 哈希表+链表(保证有序,记录元素顺序)
LinkedHashSet底层数据结构:
三可变参数
数据类型确定,个数不确定时用(0--n个) 一个参数列表只能有一个,写在最后
格式: 用在方法的参数中 修饰符 返回值类型 方法名(int... 变量名) {
四Collections集合工具类 静态方法
static <T> boolean addAll(Collection<? super T> c, T... elements):往集合中添加一些元素
例子 Collections.addAll(list, 1, 2, 3, 4, 5); // 添加多个元素
static void shuffle(List<?> list): 打乱集合顺序
例子 Collections.shuffle(list); // 打乱
static <T> void sort(List<T> list): 将集合中元素按照默认规则排序 this-参数:升序 自己比较
sort方法使用前提:实现Comparble(implements Comparble<自定义的类型>),自动重写Compare To
static <T> void sort(List<T> list，Comparator<? super T> c):将集合中元素按照指定规则排序
Collections.sort(list,new comparator<>(类型){}) 这里会有自动重写 升序 o1.getAge-o2.getAge
五 其他
Collection接口: 单列集合的根接口, 规定了公共的功能
|
|_ List接口: 元素存取有序, 可重复, 有索引
| |_ Vector类: 底层数组, 有索引, 内存空间连续分配, 查询快, 增删慢, 线程安全, 效率低
| |_ ArrayList类: 底层数组, 有索引, 内存空间连续分配, 查询快, 增删慢, 线程不安全, 效率高
| |_ LinkedList类: 底层链表, 查询慢, 增删快
| |_ 遍历
| - toArray(): 可以
| - 普通for: 可以
| - 增强for: 可以
| - 迭代器: 可以
|
|_ Set接口: 元素不可重复, 无索引
|_ HashSet类: 底层哈希表, 元素无序, 元素不可重复(用hashCode()和equals()方法来判断)
| |_ LinkedHashSet类: 哈希表+链表, 同时具有HashSet的元素不重复, 链表存取有序的特点
|
|_ TreeSet类: 底层红黑树结构(存入元素时就会按照元素自然顺序排序).
|
|_ 遍历
- toArray(): 可以
- 普通for: 不可以, 没有索引, 不能用!
- 增强for: 可以
- 迭代器: 可以day04 双列集合Map<k,v> 常用方法 遍历一 Map接口: 双列集合的根接口, 规定了共性的方法
|_ HashMap类: 哈希表=数组+链表+红黑树. key无序不可重复, 可存null键null值, 线程不安全效率高
| |_ LinkedHashMap类: 哈希表+链表. 哈希表实现key不可重复, 链表实现key存取有序
|
|_ Hashtable类: 哈希表. Hash特性针对key, key无序不可重复, 不可存null键null值, 线程安全效率低
|_ TreeMap类: 红黑树结构(存入时就排序). Tree特性针对key, 可以按照key排序, 要求key具备比较性
|_ 遍历
|_ keySet(): 获取所有key组成的Set集合, 遍历Set集合拿到key, 通过Map的get(key)得到value
| |_ 对于Set<Key>的遍历
| |_ 增强for
| |_ 迭代器
|_ entrySet(): 获取所有的key和value组成的Entry对象的Set集合, 遍历出entry对象, 通过entry对象的getKey()获取对应的key, 通过Entry对象的getValue方法获取对应的value
|_ 对Set<Entry>的遍历
|_ toArray()
|_ 增强for
|_ 迭代器
二遍历Map集合