Map and Set
1.搜索树
1.1概念
二叉搜索树又称二叉排序树，他或者是一颗空树，或者是具有一下性质的二叉树
- 若它的左子树不为空 则 左子树上所有节点都小于根节点的值
- 若它的右子树不为空 则 右子树上所有节点都大于根节点的值
- 他的左右子树也分别是二叉搜索树
//创建一个 二叉搜索树类
public class BinarySearchTree{
//内部类： 树节点
static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public TreeNode root;//根节点 方便我们等下写方法的代码
}
1.2 操作-查找
如何利用代码语言 在 二叉搜索树中 查找一个 值
思路 ：
- 利用概念可以知道 左子树上的所有结点都是小于根结点的值 右子树相反
- 那么指定cur指针去遍历这一棵树时 可以对比相应的 值的大小
- 如果 遍历到的根节点 cur.key == 查找的key 直接返回 true
- 如果 遍历到的根节点 cur.key > 查找的key 证明 key比现在的要小那么让 cur往左边走
- 如果 遍历到的根节点 cur.key < 查找的key 证明 key比现在的要大那么让 cur往右边走
public boolean find(int key){
TreeNode cur = root;
while(cur!=null){
if(cur.val > key){
cur = cur.left;
}else if(cur.val < key){
cur = cur.right;
}else{
return true;
}
}
return false;
}
1.3 操作-插入
如何利用代码语言 在二叉搜索树中插入一个结点 val 这里注意 插入在尾部 不在中间插入
思路 ：
- 利用概念可以知道 左子树上的所有结点都是小于根结点的值 右子树相反
- 首先要判断 是否为空树
- 空树：即 root == null; 直接插入node root == node ;
- 不为空： 即 root !=null; 定义一个 cur 从根节点开始遍历进行判断
- 如果说 cur.val > val 那么这个值应该在 cur 的左边 cur=cur.left 继续向下遍历
- 如果说 cur.val < val 那么这个值应该在 cur 的右边 cur=cur.right 继续向下遍历
- 如果说 cur.val = val 那么返回 false 已经有这个值了
- 直到 cur 为空 遍历结束 也就可以获得 val 应该插入的位置 但是 这里有个问题 因为cur已经为空 无法获取父结点 所以这里加入一个指针 指向cur的父亲 parent
public boolean insert(int val){
TreeNode node = new TreeNode(val);
if(root == null){
root = node;
return true;
}
TreeNode cur = root;
TreeNode parent = null;
while(cur!=null){
if(cur.val > val){
parent = cur;
cur = cur.left;
}else if(cur.val < val){
parent = cur;
cur = cur.right;
}else{
return false;
}
}
if(parent.val < val){
parent.right = node;
}else{
parent.left = node;
}
return true;
}
1.4 操作-删除(重点)
如何利用代码语言 在二叉搜索树中删除一个结点 val 这里注意 情况很多 慢慢分析
思路：
首先肯定是找到val在这一棵树中的位置 那么我们指定一个指针cur来遍历二叉搜索树
找到 指定要删除的cur后 分为三种情况
如果 要删除的结点 左边是空的 即为 cur.left == null
又 分为了三种情况 cur 是否 等于 根节点 root
- cur == root 这里直接让 根节点指向 cur.right root = cur.right;
- cur != root 这里又分为两种情况 分别是 cur在 左边 还是在 右边 那么 这里跟插入时一样 需要一个指针parent 来指向 cur的父节点
- 如果 cur = parent.left , parent.left = cur. right
- 如果 cur = parent.right, parent.right= cur. right;
如果 要删除的结点 右边是空的 即为 cur.right== null
又 分为了三种情况 cur 是否 等于 根节点 root
- cur == root 这里直接让 根节点指向 cur.left ; root = cur.left;
- cur != root 这里又分为两种情况 分别是 cur在 左边 还是在 右边
- 如果 cur = parent.left , parent.left = cur. left
- 如果 cur = parent.right, parent.right= cur. left;
如果 要删除的结点 两边都不是空的 即为 cur.right != null && cur.left != null
这里用到一个方法 叫做 替换法 如何理解呢
将 要删除的值 与 其左子树的 最右边值 或者 其 右子树的最左边值 进行 替换
这里要 理解一下：
- 因为概念可以知道 其左右子树分别也为二叉搜索树
- 左子树的最右边值 为 左子树中最大值 也就是 小值中的最大值
- 右子树的最左边值 为 右子树中最小值 也就是 大值中的最小值
通过遍历的手段去寻找最左边值或是最右边值
那么替换结束后呢 删除 最左边值或最右边值（根据你替换的决定）
这里可以直接想 上面的 删除方法 思路是一样的 但是 替换过程中 需要用到两个指针 分别代表 要替换的值 targe 以及 要替换的值的父结点 targeParent 方便删除操作
public void remove(int val){
TreeNode cur = root;
TreeNode parent = null;
while(cur!=null){
if(cur.val > val){
parent = cur;
cur = cur.left;
}else if(cur.val < val){
parent = cur;
cur = cur.right;
}else{//找到了需要删除的值
removeNode(parent,cur);
}
}
public void removeNode(TreeNode parent,TreeNode cur){
if(cur.left == null){
if(cur == root){
root = cur.right;
}else if(cur == parent.left){
parent.left = cur.right;
}else if(cur == parent.right){
parent.right = cur.right;
}
}else if(cur.right == null){
if(cur == root){
root = root.left;
}else if(cur==parent.left){
parent.left = cur.left;
}else if(cur==parent.right){
parent.right = cur.left;
}
}else{// 左右都不为空的情况 使用 替换法 这里找的是右数的最左边值
TreeNode targe = cur.right;
TreeNode targeParent = cur;
while(targe.left!=null){
targeParent = targe;
targe = targe.left;
}
if(targe == targeParent.left){
targeParent.left = targe.right;
}else if(targe == targeParent.right){
targeParent.right = targe.right;
}
}
}
1.5 性能分析
插入和删除的操作过程中都必须先查找 ，查找效率代表了二叉搜索树中各个操作的性能
对于 有 n 个结点的二叉搜索树 ，如果每个元素查找的效率相等 ，则二叉搜索树平均查找长度是结点越多 比较次数越多
最优情况下 二叉搜索树为 完全二叉树 则 其平均比较次数为 树的高度 即为 logN
最优情况下 二叉搜索树为 单支树 则 其平均比较次数为 即为 N/2
如何去 优化 使得二叉树 不论按照什么次序插入关键码 都可以让 二叉搜索树的性能达到最佳？
那么这里介绍
TreeMap 和 TreeSer
他们是在 java中 使用搜索树 来实现的 Map 和 Set ；
实际上用的是 红黑树 这是一种近似平衡的二叉搜索树
在二叉搜索树的基础上 增加颜色以及 红黑树性质验证 后面介绍
2. 搜索
Map 和 Set 是一种专门用来 进行搜索的数据结构 可以理解成容器
通过之前的学习 大概搜索方式有两种
- 直接遍历搜索 找到要找的元素输出 时间复杂度为O(N)，如果元素比较多 效率就很慢
- 二分查找 时间复杂度是 O(logN)，要求数组必须有序
这里大概说一下这个二分查找 想要使用二分查找是有条件的 必须是有序的数组
设定一个 left 和 right 指针分别指向 数组的头和尾
然后找到 数组 下标中间的值 mid = （left+right)/2
比较 需要查找的数字val 和 数组mid下标 的值
如果 val > array[mid] 证明 val 在中间值的 右边 这时我们就缩短比较的区间 让 left = mid + 1
如果 val < array[mid] 证明 val 在中间值的 左边 这时我们就缩短比较的区间 让 right = mid-1
public int binarySearch(int[] array,int val){
int left = 0;
int right = 0;
while(left<=right){
int mid = (left+right)/2;
if(val>array[mid]){
left = mid + 1;
}else if(val < array[mid]){
right = mid - 1;
}else{
return mid
}
}
return -1;
}
那么以上两种方法无法对以下这些事情进行排序
- 根据姓名查找考试成绩
- 通讯录
- 不重复集合 需要先查找关键字是否已经在集合中
可能在 查找的过程当中还会 采取一下插入和 删除的操作 即为 动态查找
2.1模型
一般把搜索的数据 称之为 关键词 Key 和关键词对应的 称之 值
- 纯Key模型 只有关键字没有值的 适合一下场景
- 快速查找某个名字是否在通讯录中
- 快速查找一个单词 是否在词典中
- Key-Value模型 关键字 对应 值 的模型
- 学生对应自己的考试成绩
- 统计文件中每个单词出现的次数
Map中存储的就是 key-value 的键值对 ， Set只存储了key
3. Map的使用
[Map的官方文档](Map (Java Platform SE 8 ) (oracle.com))
3.1关于Map的说明
Map 是一个接口类 该类没有继承子 Collection 该类存储的是 <K,V> 结构的键值对，并且K是唯一的不能重复
3.2 关于Map.Entry<K,V>的说明
Map.Entry<K,V> 是 Map 内部实现的一种内部类 跟下面这种内部类类似
这里的 K V 都是泛型 我这边只是用 int 代替写一下
static class Node{
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
public int getKey(){
return this.key;
}
public int getVal(){
return this.val;
}
}
不过 有相应的方法 这里介绍一下
| 方法 | 解释 |
|---|---|
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 将键值对中的value替换为指定value |
注意：Map.Entry并没有提供设置Key的方法
这边先了解一下使用方法
3.3Map的常用方法
| 方法 | 解释 |
|---|---|
| V get(Object key) | 返回 key 对应的 value |
| V getOrDefault(Object key, V defaultValue) | 返回 key 对应的 value，key 不存在，返回默认值 |
| V put(K key, V value) | 设置 key 对应的 value |
| V remove(Object key) | 删除 key 对应的映射关系 |
| Set keySet() | 返回所有 key 的不重复集合 |
| Collection values() | 返回所有 value 的可重复集合 |
| Set<Map.Entry<K,V>> entrySet() | 返回所有的 key-value 映射关系 |
| boolean containsKey(Object key) | 判断是否包含 key |
| boolean containsValue(Object value) | 判断是否包含 value |
注意：
- Map是一个接口，不可以实例化对象，如果要实例化对象只能实例化实现他的类 比如 TreeMap 和 Hash Map
- TreeMap中存放键值对的是 Key 是唯一的 value 是可以重复的
- TreeMap 中插入键值对 Key是 不可以为空 否则会抛出异常
NullPointerException空指针异常 但是 val 是可以为空的 HashMap的 Key 和 Val 都是可以为空的- Map中所有的 Key 可以全部分离出来 存储到Set中进行访问 上面第5个方法 就是用于 提取Key的
- Map中的value 也可以全部分离出来，存储在 Collection的任何一个子集合中？（这里注意 val是可以重复的）
- Map中键值对的Key不可以直接修改 但是 value 可以直接修改 ，如果想要修改Key 只能先删掉 然后重新插入
这里有个重要的点 因为 TreeMap的底层是 红黑树 所以 在插入 删除 查找之前 跟 二叉搜索树一样 会先进行比较 如果是 Integer类型 就直接比较 如果是 char类型也是如此 string类型是先比较首字母
所以 这里就有一个注意点 ： TreeMap 的 Key 必须是一种 可以比较的类型 可以 用继承来写
| Map的底层结构 | TreeMap | HashMap |
|---|---|---|
| 底层结构 | 红黑树（二叉搜索树） | 哈希桶 |
| 插入/删除/查找 时间复杂度 | $O(log_2 N)$ | $O(1)$ |
| 是否有序 | 关于Key有序 | 无需 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找 的区别 | 进行元素比较后插入 | 直接利用哈希函数计算插入 |
| 比较与覆写 | key必须可以进行比较否则会异常 | 自定义类型需要覆写 equals和 hashCode 方法 |
| 应用场景 | 需要Key的情况下 | 不关心Key是否有序 需要更高的时间性能 |
3.4 TreeMap 的使用案例
4.Set的说明
[set的官方文档](Set (Java Platform SE 8 ) (oracle.com))
Set 与 Map 不同的点 在于 Set 是继承 Collection 的 接口类 ，Set 中 只存储了Key
4.1常见方法
| 方法 | 解释 |
|---|---|
| boolean add(E e) | 添加元素，但重复元素不会被添加成功 |
| void clear() | 清空集合 |
| boolean contains(Object o) | 判断 o 是否在集合中 |
| Iterator iterator() | 返回迭代器 |
| boolean remove(Object o) | 删除集合中的 o |
| int size() | 返回set中元素的个数 |
| boolean isEmpty() | 检测set是否为空，空返回true，否则返回false |
| Object[] toArray() | 将set中的元素转换为数组返回 |
| boolean containsAll(Collection c) | 集合c中的元素是否在set中全部存在，是返回true，否则返回 false |
| boolean addAll(Collection c) | 将集合c中的元素添加到set中，可以达到去重的效果 |
注意：
- Set是继承自 Collection 的一个接口类
- Set 中 只存储了 Key 并且要求Key一定要唯一
- TreeSet 的底层是 用 Map来实现的 其使用 Key 与 Object 的一个默认对象座位键值对插入到 Map 中
- Set 最大的功能就是对集合中的元素进行去重
- 实现 Set接口的常用类有 TreeSet 和 HashSet 还有一个 LinkedHashSet，LinkedHashSet 他两 是在HashSet的基础上 维护了一个双向链表来记录元素的插入次序
- Set中的Key不能修改 跟 Map一样 只能删除后重新插入
- TreeSet中的 Key 不可以为空值
- TreeSet 和 HashSet 的区别
| Set的底层结构 | TreeSet | HashSet |
|---|---|---|
| 底层结构 | 红黑树（二叉搜索树） | 哈希桶 |
| 插入/删除/查找 时间复杂度 | $O(log_2 N)$ | $O(1)$ |
| 是否有序 | 关于Key有序 | 不一定有序 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找 的区别 | 进行元素比较后插入 | 利用哈希函数计算后插入 |
| 比较与覆写 | key必须可以进行比较否则会异常 | 自定义类型需要覆写 equals和 hashCode 方法 |
| 应用场景 | 需要Key的情况下 | 不关心Key是否有序 需要更高的时间性能 |
4.2 TreeSet的使用案例
5.哈希表
5.1 概念
在 顺序表 跟 平衡树中 我们发现 元素关键码与其存储的位置 没有对应关系 所以 在 查找一个元素的时候 必须经过多次的比较以及遍历 顺序表 的时间复杂度为 $O(N)$ 平衡树的时间复杂度则是 树的高度 即 $O(log_2 N)$ 搜索的效率取决于 搜索过程中的元素比较次数
理想办法：可以不经过比较一次就得到想要的元素 如果 构造一种存储结构 通过某种函数 使得 元素的存储位置 与 他的关键码 之间 存在 一 一 映射的关系 那么在查找是 通过该函数就可以快速找到该元素 （一一映射 的意思是 函数 x = y）
当 向这种结构 中：
-
插入元素：
根据待插入元素的关键码 ，计算出 该元素 存储位置 并 按此进行存放
-
搜索元素：
对关键码进行运算，求得的值 就是 存放位置
该方法 即为 哈希(散列)方法 ， 哈希方法中使用的 转换函数 成为 哈希函数，构造出来的结构成为 哈希表
例如 ： 数据集合 {1，7，6，4，5，9}
哈希函数 设置为 hash(Key) = key % capacity , capacity 是存储元素底层空间总的大小
这时 向这个列表中 插入元素 44 ， 44%10 = 4
但是 下标4 中已经有 对应值 这就是 哈希冲突
5.2 哈希冲突
5.2.1 冲突-概念
对于两个数据元素的关键词 K1 != K2 但是 Hash(K1) == Hash(K2)
即为 不同的关键词通过函数 算的哈希地址相同 这种现象我们叫 哈希冲突或者是 哈希碰撞
由于 哈希表底层数组的容量往往小于实际要存储的关键词数量，这就导致一个问题
冲突是必然的
但我们能做的只有 降低冲突率
那如何降低 冲突率呢 这里介绍两个方法
- 重新设计我们的 哈希函数 ，使得哈希函数设计更合理
一般情况下 很少会自己去设计 一般都是 直接用的java自带的
- 负载因子调节法
5.2.2 冲突-避免-负载因子调节（重点）
这里只需要知道两件事
-
散列表的负载因子 α 定义公式为
设 填入表中元素个数为 usedSize 散列表的长度为 array.length
$$
α = usedSize / array.length
$$ -
负载因子大概在 0.7 - 0.8 以下 java系统库中 将其限制在了 0.75 超过将调整 散列表
在一直哈希表中关键字个数不可改变的情况下，我们只能调整哈希表中的数组大小来调整散列表
这里说一下如何扩容
难点：我们扩容是将哈希表扩容到原来的两倍 那么如果哈希表的容量变化了 哈希函数所算出来的值也会出现变化 这里就有必要注意了
思路：扩容的时候我们新建一个数组来代表扩容后的哈希表 遍历原函数 重新计算原数组中的 哈希函数的值 然后放入我们新的数组中 最后将原数组的指向改变
解决哈希冲突的 办法 ：1. 闭散列 2. 开散列
闭散列没必要 有想要了解的去找ai
我们直接学习开散列
5.2.3 冲突-解决-开散列/哈希桶（重点）
理论： 开散列法又叫链地址法 ，首先对关键码利用 哈希函数计算 散列地址 ，具有相同地址的关键码归与一个子集合 ，每一个子集合称为一个桶，各个桶中元素通过一个单链表链接起来，各链表的头节点存储在 哈希表中
开散列可以理解成在一个大集合中的搜索问题转化在小集合中搜索了
5.2.3.1 小型优化方案
刚刚提到 开散列可以理解成在一个大集合中的搜索问题转化在小集合中搜索 那还是会出现 性能有时不佳的情况 那我们就可以 在这个小集合中进行优化 也就是 优化哈希桶
- 每个桶 背后 都是一个哈希表
- 每个桶背后都是一颗搜索树
5.3 实现
public class HashBuck{
static class Node{
public int key;
public int val;
public Node next;
public Node(int key,int val){
this.key = key;
this.val = val;
}
}
public Node[] array;//这个是 哈希表
public int usedSize;//用于记录存放元素的个数 用于计算负载因子
public HashBuck(){
array = new Node[10];//给一个初始容量
}
//头插法
public void putHead(int key,int val){
Node node = new Node(key,val);
int index = key % array.length;// 哈希函数
Node cur = array[index];//用一个指针来指向哈希桶的头
//这里如果找到了原来就有的 key的话 就更新key指向的val值
while(cur!=null){
if(cur.key == key){
cur.val = val;
return;
}
}
//头插法
node.next = array[index];
array[index] = node;
usedSize++;
//插入时你要判断 是否已经达到负载因子的最大值
if(loadFactor()>=0.75){
//如果已经达到负载值 就要进行扩容 调整
risize();
}
}
public double loadFactor(){
return usedSize*1.0/array.length;
}
//扩容
private void resize(){
Node[] tmpArr = new Node[array.length*2];//
//遍历原数组
for(int i = 0;i<array.length;i++){
Node cur = array[i];
//遍历哈希桶内的链表
while(cur!=null){
Node curNext = cur.next;
//计算新的哈希函数值
int newIndex = cur.key % tmpArr.length;
//头插法
cur.next = tmpArr[newIndex];
tmpArr[newIndex] = cur;
cur = cur.next;
}
}
array = tmpArr;
}
//获取key的val值
public int get(int key){
int index = key % array.length;
Node cur = array[index];
while(cur!=null){
if(cur.key == key){
return cur.val;
}
}
//没找到
return -1;
}
}
5.3.1 引用类型的实现
上面是 int类型 的实现 现在写一下 引用类型的实现
有什么注意点？
注意：
- 在计算哈希值的时候 引用类型无法直接进行计算 需要在所引用的类型中重写 hashCode() 的方法 达到自己想要的结果
- 在比较 key 是否有 重复项的时候 int类型可以直接 cur.key == key 来进行判断 但是引用类型不可以直接判断 而是用 equals方法 所以 想要达到自己想要的效果最好还是 重写 equals 方法
public class HashBuck2<K,V> {
static class Node<K,V>{
public K key;
public V val;
public Node next;
public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
//哈希表
private Node<K,V>[] array;
private int usedSize;
private static final double LOAD_FACTOR = 0.75;
//构造方法
public HashBuck2(){
array = (Node<K, V>[])new Node[10];//这里要注意写法 具体原因不知道 后面了解
}
public void put(K key,V val){
int hash = key.hashCode();
int index = hash % array.length;//不用担心越界 因为除数是10的情况下 余数不会大于10
Node<K,V> cur = array[index];
while(cur!=null){
if(cur.key.equals(key)){
cur.val = val;
}
}
Node<K,V> node = new Node<>(key,val);
node.next = array[index];
array[index] = node;
usedSize++;
}
6.leetCode 题目
6.1 只出现一次的数字
思路：
6.2 复制带随机性指针的链表
思路： 这个思路有妙
- 首先这个题目要复制一个链表 这里的意思是复制链接方式 而不是复制地址 所以这里就有一个问题 如何让我们的链接方式复制过去？
- 这里利用Map的 key-value特性
- 在 一个新的 map 中 将 旧链表和 新链表的 地址 一 一对应
- 利用cur指针遍历链表 将 旧链表的节点地址赋值为 key 新链表的节点地址赋值为 val 注意 其实来到这里以后 还是没有形成链表 各个节点 的next并没有指向
- 然后再次遍历 将新链表节点的指向 跟 旧链表节点的 指向重合 就可以了
6.3 宝石与石头
思路：
- 利用好 Set搜索快的好处 将 宝石 放进 Set 中
- 遍历 石头 与 Set中元素进行比较 相同则 有效值+1
6.4 坏键盘打字
思路：
- 这里其实 跟 宝石与石头这题刚好相反 他要你找出 坏掉的键盘
- 思路很简单 还是利用好 Set 的特性 将输出的字母 放入 Set1 中 跟 输入的字母进行比较 不一样的 则输出
- 但是这里有一个坑人的点 就是 你这样子输出 是会有重复的 题目要求不重复
- 解决办法： 多建立一个 Set2集合结构 把 刚刚输出的那些 重新放入 Set 中 然后 跟 Set1 比较的同时 跟 Set2 也要比较 同时达成两个都没有相同的情况下 输出
6.5 前K个高频单词
思路：代码有点长 搞清楚思路 有点难
建议是明天上课在看一遍
17课 1.50-2.25是第五题的讲解 2.30-2.50源码讲解
常量池的讲解
String s1 = "hello";
String s2 = "hello";
System.out.print(s1 == s2);//true
String s3 = new String("hello");
String s4 = new String("hello");
System.out.print(s3 == s4);//false
System.out.print(s1 == s3);//false
char[] ch = new char[]{'a','b','c'};
String s1 = new String(ch);
String s2 = "abc";
System.out.print(s1 == s2);//false