# Set集合
1. 特点
1). 不可重复元素
2). 没有索引
3). 不保证存取顺序
(Set没有特有方法)
2. 功能
Set<String> set = new TreeSet<>();
1).添加元素 set.add("ccc");
2).遍历元素
I. 迭代器遍历
Iterator<String> it = set.iterator();
while(it.hasNext()){
String e = it.next();
sout(e);
}
II.增强for循环(foreach)
for (String e : set) {
sout(e);
}
III.不能使用fori普通循环
# TreeSet集合
1. TreeSet集合特点
1). 不可以存储重复元素
2). 没有索引
3). 可以将元素按照规则进行排序
I. TreeSet():根据其元素的自然排序进行排序
II. TreeSet(Comparator comparator):根据指定的比较器进行排序
两种方式:匿名内部类、Lambda
2. 注意
1). TreeSet如果直接存元素,这个元素类型必须实现Comparable接口
否则
ClassCastException: cannot be cast to
解决:在类中实现Comparable接口,并重写CompareTo方法
2). 默认规则
Integer,String 内部都实现了Comparable接口
Integer的默认规则时升序
String的默认规则是按ASCII码表顺序
Ax、ae、b、bc、bcc、bcd
3. 运用
1). 自然排序Comparable
2). 比较器排序Comparator
两种比较总结
# 数据结构——树
1. 树的特点
1). 根节点只有一个,并且在最上面
2). 每个节点都可以有子节点(分支)
3). 没有子节点的节点成为叶子节点
4). 层高:节点的层级数量
2. 二叉树
概述:每个节点最多两个子节点
3. 二叉查找树
1). 特点:左小右大
2). 内含:二分查找
4. 二叉查找平衡树
1). 特点
左右平衡,以降低层高,提高查找要求
左右高度差不能超过1
2). 旋转
I. 目的:为了保证以上高度差规则
II. 规则:⭐
左子树高,就右旋
右子树高,就左旋
3). 注意
提高查找的效率是减少增删的性能
# 红黑树——TreeSet的核心数据结构
1. 特点
元素按大小顺序:升降序可以自定义(适合排序)
1). 左右子树高度差可能大于1
2). 左右子树高度不会超过2倍
2. 红黑规则
# HashSet集合
1. 特点
1). 底层数据结构是哈希表
2). 存取无序
3). 不可以存储重复元素
4). 没有索引,不能进行普通for循环
2. TreeSet
判断元素重复的原理
1). 比较规则
o1 - o2 升序
o2 - o1 降序
2). 元素重复
o1 - o2, 这两个元素就是相同元素
3. hashSet:判断元素重复的原理
1). 结论:
先比较hashCode,如果hashCode一致,在进行equals
如果eauals为true,就被认为是重复元素
2). hashCode -> 5.hashCode
3). 哈希表 -> #哈希表
4. toString方法
调用了hashCode()方法
5. hashCode
1). 源码
public native int hashCode();
// 这是一个本地方法,在java没有源码,因为它的源码在JVM底层,是用C/C++编写的
2). Object类中的hashCode算法
I. 算法内容
对'对象'的真正的内存地址进行计算,得到一个hash值
II. 算法特点
对象的内存地址(无穷多个,因地址受限) -> 哈希值有限(约为43亿)
可能: 两个不同的对象 -> 相同的哈希值
=> 哈希碰撞/哈希冲突
对象A -> 哈希值1
对象b -> 哈希值2
这个算法会尽量让哈希值1和哈希值2尽量不相等(散列)
III. String类重写hashCode算法(31算法:每个过程都有31参与)
char[] value = {'a', 'b', 'c'};
h = 0;
第一次遍历: h = 31 * 0 + 97 = 97;
第二次遍历: h = 31 *97 + 98 = 3105;
第三次遍历: h = 31 * 3105 + 99 = 96354;
# 哈希表
1. 底层数据结构
1). JDK8之前: 数组 + 链表
2). JDK8以及之后 : 数组 + 链表/红黑树
2. 默认状态
数组长度: 16
默认加载因子: 0.75
3. 特点
数组存hashCode不同的元素
链表/红黑树:存hashCode相同的元素
当链表长度超过8时,就会转为红黑树(平衡查找和增删性能)
4. 扩展
1). 链表存的是 元素哈希值%数组长度 一致的元素
2). 扩容: 当数组被使用了 16 * 0.75 = 12, 数组就会扩容(2倍)
5. 原理
先比较hashCode%数组长度,如果余数不一致,存数组
如果余数一致,接着判断equals,如果为false,存链表/红黑树
如果equals也会true,则不存
6. 情况
1). 情况一:Student有没有重写Object类的hashCode和equals方法
Object类的hashCode方法
将 对象真正内存地址 -> 哈希值
不同对象 -> 一般产生不同的哈希值
2). 假设hashCode碰撞了,equals必然不会相同
因为Object类的equals比较的内存真正地址
3). 需求: 在实际需求中,我们一般认为所有属性都一致的对象就是同一个对象
4). 解决:
Student重写hashCode跟equals方法
(这两个方法都要跟属性挂钩)
快捷键: alt + insert -> equals and hashcode
# Map集合
1. 概述
interface Map<K, V> k:键的类型 V:值的类型
2. 特点
1). 双列集合,一个键对应一个值(Key,Value)
2). 键不可以重复,值可以重复
3. 基本使用
Map<String, String> map = new HashMap<String, String>();
map.put("itheima001", "林青霞");
map.put("itheima002", "张曼玉");
map.put("itheima003", "张敏");
// {itheima03=张敏, itheima001=林青霞, itheima02=张曼玉}
System.out.println(map);
// 如果key重复,那么新value覆盖旧value
map.put("itheima001","王祖贤");
// 删除kep为002的值
remove.put("itheima002");
// {itheima03=张敏, itheima001=王祖贤}
System.out.println(map);
// 集合元素的个数
int size = map.size();
// 2
System.out.println(size);
// 清空所有元素
map.clear();
// 判空
boolean result = map.isEmpty();
containsKey
containsValue
4. Map的遍历
1). 第一种遍历方式: 键找值
I. 获取map集合所有键 keySet
II. 然后遍历keySet(迭代器/增强for循环),去除每一个key
III. 在map,用key找value
2). 第二种遍历方式: 键值对
I. 获取Map的键值对集合 entrySet
entry(一个键,一个值)
Set<Map.Entry<Integer,String>> entrySet = map.entrySet();
II. 遍历entrySet(迭代器/增强for),取出每一个entry
for(Map.Entry<Integer,String> entry : entrySet) {
III. 从entry获取key/value
Integer
}
5. HashMap集合
1). 数据结构: 哈希表
数组 + 链表
2). HashSet底层用的就是HashMap的key这一列
3). 遍历
II. 第二种遍历
Set<Map.Entry<String, Student>> entrySet = map.entrySet();
6. map的forEach()方法
7. TreeMap集合
1). 数据结构: 红黑树结构
2). 以来自然排序或者比较器排序,对键进行排序
3). 如果键存储的是自定义对象,需要实现Comparable接口或者在创建TreeMap对象时候给出比较器排序规则