常见的数据结构:栈 ,队列 ,数组 ,链表和红黑树
栈: stack,又称堆栈,是一种 运算受限 的线性表
特点: 1.先进后出
2.栈的入口,出口都是栈的顶端位置
队列: queue 也是一种 运算受限 的线性表
特点: 1.先进先出
2.队列的入口,出口各占一侧
数组: Array,有序的元素序列
特点: 1.查找元素快(通过索引)
2.增删元素慢(需要创建新数组)
链表: linked list,由节点node(链表中每个元素称为节点)组成,节点可以在运行时i动态生成.
每个节点包括两个部分: 一个是存储数据元素的数据域
另一个是存储下一个节点地址的指针域.包括单向和双向链表.
特点: 1. 多个节点之间,通过地址进行链接
2. 查找元素慢
3. 增删元素快
红黑树: binary tree,是每个节点不超过2的有序树(tree)
红黑树的约束:
1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
特点: 速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍
List接口:
特点:
1. 它是一个存取有序的集合;
2. 带有索引
3. 集合中可以有重复的元素,通过元素的equals方法.来比较是否为重复的元素
常用方法:
[Java] 纯文本查看 复制代码
pubilc void add (int index, E element) : 将指定的元素,添加到该集合中的指定位置上.
public E get (int index) : 返回集合中指定位置的元素.
public E remove (int index) : 移除列表中指定位置的元素,返回的是被移除的元素.
Public E set (int index, E element) : 用指定元素替换集合中指定位置的元素,返回值的更新前的元素.
ArrayList集合的特点:
ArrayList底层的数据结构:数组
特点:
查询快
增删慢
线程不安全,效率高
使用场景:
存储的数据查询多,增删少的场景
LinkedList集合的特点:
LinkedList底层的数据结构:链表
特点:
查询慢
增删快
线程不安全, 效率高
适用场景:
存储的数据查询少, 增删多的场景
特有成员方法(主要操作开头和末尾元素):
[Java] 纯文本查看 复制代码
void addFirst(E e): 将指定元素插入此列表的开头[/size][/font][/align][align=left][font=微软雅黑][size=3]void addLast(E e): 将指定元素添加到此列表的结尾
E getFirst(): 返回此列表的第一个元素
E getLast(): 返回此列表的最后一个元素
E removeFirst(): 移除并返回此列表的第一个元素
E removeLast(): 移除并返回此列表的最后一个元素
E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中
Vector集合
Vector底层的数据结构:数组
Vector的特点:
查询慢
增删快
线程安全, 效率低
Vector目前几乎没人使用
Set集合体系
HashSet集合
Set集合体系特点:
1. 元素不可重复
2. 没有索引
HashSet特点:
1. 元素不可重复
2. 没有索引
3. 元素存取无序 (存入和取出顺序有可能不一致)
4. 底层采用 哈希表 结构. (查询快)
哈希表 = 数组 + 链表或红黑树
常用方法:
[Java] 纯文本查看 复制代码
boolean add(E e): 添加元素, 根据元素的
hashCode()和equals()方法判断是否重复. 重复则不添加并返回false, 不重复则添加并返回true
哈希值:
一个十进制数值, 一般是通过将该对象的内部地址转换成一个整数来实现的
public native int hashCode();
可以调用系统本地代码(C++)计算出一个对象地址的哈希值hashCode()方法的作用
方法内部的算法用于将对象计算为一个哈希值, 便于根据哈希值比较对象是否"相等"
哈希值主要是为了提高对象存储在 哈希表 中的效率
注意:
1. 如果我们不满意Object中的哈希值计算方法, 可以重写hashCode()方法.
但在Java代码中不能直接重写带有 native 的方法, 重写时应该将native 去掉
@Override
public int hashCode() {}
2. hashCode() 方法有可能将"不同的对象"计算出"相同的哈希值", 这称为"哈希冲突",
在出现冲突后, 一般再通过 equals() 方法来继续判断对象是否"相等
HashSet集合存储数据的结构: 哈希表
哈希表 = 数组+链表/红黑树
可变参数
JDK 5 出现. 指同一个类型参数个数可变的参数
可变参数的本质就是一个"数组"
格式: 用在方法的参数中
修饰符 返回值类型 方法名(参数类型... 变量名) {
// 可以直接将 变量名 当作 数组名 使用
}
注意事项:
1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
2. 一个方法的参数列表中, 只能有一个可变参数
3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
Collections集合工具类
Collections集合工具类: addAll(), shuffle()
java.util.Collections类: 操作集合的工具类
静态方法:
[Java] 纯文本查看 复制代码
static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素
static void shuffle(List<?> list) :打乱集合顺序
static <T> void sort(List<T> list) :将集合中元素按照默认规则排序
static <T> void sort(List<T> list,Comparator<? super T> ) :将集合中元素按照指定规则排序
Collections集合工具类: sort(List list)
sort(List<T> list): 默认按照"升序"将元素排序. 数字, 字母, 都可以按照升序排序 自定义JavaBean对象默认不能排序, 因为不知道如何比较哪个对象大, 哪个对象小
自定义JavaBean对象要想排序, 需要实现 Comparable<E> 接口, 重写 int compareTo(E e) 方法
大小的比较通过 compareTo() 方法的返回值确定:
负数: 当前元素比被比较元素小
0: 当前元素与被比较元素相等
正数: 当前元素比被比较元素大
规则:
this-参数: 升序
参数-this: 降序
Comparable接口和Comparator接口区别
Comparable: 让JavaBean自身具有可比较性 (自己和其他人比)
Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)
Comparator使用方式:
定义类作为比较器, 实现Comparator接口, 重写int compare(E o1, E o2)方法, 泛型为要比较的元素的类型
在Collections.sort(List<T> list,Comparator<? super T>)方法中传入自定义比较器对象
规则:
o1-o2: 升序
o2-o1: 降序
java.util.Map接口: 双列集合的顶层
成员方法:
[Java] 纯文本查看 复制代码
V put(K key, V value): 添加/修改键值对. 如果键存在, 则用新值替换已有值
V remove(Object key): 根据键删除键值对, 返回被删除元素的值
V get(Object key): 根据键获取值. 如果键不存在, 则返回null
boolean containsKey(Object key): 判断是否包含指定的键
Set<K> keySet(): 获取Map集合中所有的键, 存储到Set集合中
Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)
JDK 9对于集合初始化的优化
java.util.List
静态方法
static List<E> of(E... e): 返回包含指定元素的 不可变List 集合
java.util.Set
静态方法
static Set<E> of(E... e): 返回包含指定元素的 不可变Set 集合
java.util.Map
静态方法
static Map<K, V> of(K k1, V v1): 返回包含指定键值对的 不可变Map 集合
Map集合概述:
java.util.Map<K, V>接口
Map集合特点:
1. 是双列集合, 一个元素包含两个值 (键key, 值value)
2. key和value的类型可以相同, 也可以不同
3. key不允许重复, value可以重复
4. key和value是一一对应的, 一个键只能对应一个值
Map集合适合存储一对一关系的数据
Map常用子类:
java.util.Map<K, V>接口: 双列集合的根接口, 规定了共性的方法
|_ HashMap<K, V>类: 底层哈希表. key存取无序不可重复
|_ LinkedHashMap类: 底层哈希表+链表. key存取有序不可重复
映射: 键和值的对应关系 mapping
HashSet底层使用的就是HashMap
LinkedHashSet底层使用的就是LinkedHashMap
Map中常用方法:
Map<String, Phone> map = new HashMap<>();
map.put("张三", p1);
map.put("张三", p2);
java.util.Map接口: 双列集合的顶层
成员方法
[Java] 纯文本查看 复制代码
V put(K key, V value): 添加/修改键值对. 如果键存在, 则用新值替换已有值
V remove(Object key): 根据键删除键值对, 返回被删除元素的值
V get(Object key): 根据键获取值. 如果键不存在, 则返回null
boolean containsKey(Object key): 判断是否包含指定的键
Set<K> keySet(): 获取Map集合中所有的键, 存储到Set集合中
Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的Entry对象的集合(Set集合)
Map遍历方式一:keySet()方法实现通过键找值
Set<K> keySet(): 获取Map集合中所有的键, 存储到Set集合中
keySet()遍历步骤:
1. Map对象调用 keySet() 方法, 获取包含所有key的Set集合
2. 遍历Set集合, 获取每个key
3. 通过Map对象调用 get(Object key) 方法根据key获取到value
[Java] 纯文本查看 复制代码
Map<String, String> map = new HashMap<>();
// keySet()遍历
Set<String> keys = map.keySet();
for (String key : keys) {
// 通过每个键获取值
String value = map.get(key);
// 打印当前键值对
System.out.println(key + "=" + value);
}
Entry键值对对象介绍:
java.util.Map.Entry接口:
常用成员方法:
K getKey(): 获取Entry对象中的键
V getValue(): 获取Entry对象中的值
Entry对象就是一个节点, 节点中存储了key和value
拿到一个Entry对象就可以从中获取key和value
HashMap中Entry实现类
[Java] 纯文本查看 复制代码
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
}
java.util.Map接口
Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)
Map遍历方式二:通过entrySet()获取对象形式遍历:
java.util.Map接口
Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)
entrySet()方法遍历Map步骤:
1. Map对象调用 entrySet() 获取包含所有Entry对象的Set集合
2. 遍历Set集合, 获取每个Entry对象
3. 调用Entry对象的 getKey() 和 getValue() 方法获取键和值
[Java] 纯文本查看 复制代码
Map<String, String> map = new HashMap<>();
// keySet()遍历
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry<String, String> entry : entries) {
// 通过Entry对象获取每个键值对
String value = entry.getKey();
String value = entry.getValue();
// 打印当前键值对
System.out.println(key + "=" + value);
JDK9对集合添加的优化:
使用集合添加大量元素时, 反复add(...)比较麻烦. JDK 9 为集合提供了一些静态方法, 可以方便的对集合进行初始化
java.util.List
静态方法:
static List<E> of(E... e): 返回包含指定元素的 不可变List 集合
java.util.Set
静态方法
static Set<E> of(E... e): 返回包含指定元素的 不可变Set 集合
java.util.Map
静态方法
static Map<K, V> of(K k1, V v1, ...): 返回包含指定键值对的 不可变Map 集合
注意:
1. of() 方法只适用于List接口, Set接口, Map接口, 不适用于接接口的实现类
2. of() 方法的返回值是一个不能改变的集合, 集合不能再使用 add(), put() 方法添加元素, 会抛出异常
3. Set接口和Map接口在调用 of() 方法的时候, 不能有重复的元素, 否则会抛出异常
将 不可变集合 的元素转移到常见集合实现类中:
List
[AppleScript] 纯文本查看 复制代码
ArrayList<Integer> list = new ArrayList<>(List.of(1,2,3));[/align] Set
HashSet<Integer> set = new HashSet<>(Set.of(1,2,3));
Map
HashMap<Integer, String> map = new HashMap<>(Map.of(1,"a",2,"b"));
今日目标:
能够说出Map集合特点:
Map接口双列集合的顶层
特点:
Map存储元素是键值对方式(key-value)
Map中key不能重复(唯一), 键值对是一一对应的, 一个键对应一个值
使用Map集合添加方法保存数据:
map.put(键, 值);
添加键值对: map中没有这个键时, 返回null
修改键值对: map中已经有该键, 返回的是被替换的值
使用”键找值”的方式遍历Map集合:
[Java] 纯文本查看 复制代码
keySet()
Set keySet = map.keySet();
for (键的类型 key : keySet) {
// 通过键获取值
值的类型 value = map.get(key);
}
使用”键值对”的方式遍历Map集合:
[Java] 纯文本查看 复制代码
Entry对象[/align][align=left]Set<Entry> entrySet = map.entrySet();[/align]
[align=left]for (Entry entry : entrySet) {[/align]
[align=left]// 通过entry对象获取键和值[/align]
[align=left]键的类型 key = entry.getKey();[/align]
[align=left]值的类型 value = entry.getValue();[/align]
[align=left]}