搜索树
概念
这棵树的中序遍历结果是有序的
接下来我们来模拟一棵二叉搜索树，和二叉树一样，定义左右结点，结点值和根结点
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;
}查找
拿目标值key与root进行比较，比root大的往右边搜索，比root小的往左边搜索；接着继续与左/右子树根结点比较，重复上面步骤
搜索代码
public boolean search(int key){
TreeNode cur = root;
while(cur != null){
if(cur.val < key){
cur = cur.right;
} else if (cur.val>key) {
cur = cur.left;
}else{
return true;
}
}
return false;
}时间复杂度：
最好情况：完全二叉树，那时间复杂度为O(logN)
最坏情况：单分支二叉树，时间复杂度O(N)
插入
对于下方的二叉树，我们需要插入15
我们可以定义一个cur，负责遍历二叉树；定义一个parent记录子树的根结点位置
如果当前cur结点的值比目标插入的值小，就把parent定位到当前结点，把cur往右子树移动
如果cur值较大就向左子树移。cur负责帮助parent定位到目标值附近
定义一个node承载目标值，如果parent的值小于目标值就把node右插，反之则左插
public boolean search(int key){
TreeNode cur = root;
while(cur != null){
if(cur.val < key){
cur = cur.right;
} else if (cur.val>key) {
cur = cur.left;
}else{
return true;
}
}
return false;
}
public static boolean insert(TreeNode root, int val){
if(root == null){
root = new TreeNode(val);
return true;
}
TreeNode cur = root;
TreeNode parent = null;
while(cur!=null){
if(cur.val < val){
parent = cur;
cur = cur.right;
}else if(cur.val > val){
parent = cur;
cur = cur.left;
}else{
return false;
}
}
TreeNode node = new TreeNode(val);
if(parent.val>val){
parent.left = node;
}else{
parent.right = node;
}
return true;
}拿这么一个列表来测试一下
array = {5,12,3,2,11,15}
正常画出来的图是这样的
测试debug后画出来的图一模一样😊
删除
设待删除的结点是cur，而待删除结点的双亲结点是parent
第一种情况：cur.left == null
1. cur是root时，让root = cur.right
2.cur不是root，cur是parent.left，则parent.left = cur.right
3.cur不是root，cur是parent.right，则parent.right = cur.right
if(cur.left == null){
if(cur == root){
root = parent.right;
}else if(cur == parent.left){
parent.right = cur.left;
}else{
parent.right = cur.right;
}
}第二种情况：cur.right == null
1.cur是root，则root = cur.left
2.cur不是root，cur是parent.left，则parent.left = cur.left
3.cur不是root，cur是parent.right，则parent.right = cur.left
else if(cur.right == null) {
if(cur == root){
root = parent.left;
}else if(cur == parent.left){
parent.left = cur.left;
}else{
parent.right = cur.left;
}
}第三种情况：cur.left != null && cur.right != null
我们逍遥删除cur位置这个40元素
首先确定的一点是，40的左子树比40都小，右子树比40都大
替换法：找一个数据来替换cur
1.确定cur这里将来要放的数据一定比左边都大，比右边都小
2.要么在左树里面找到最大的数值（左树最右边的数据）；
要么就在右树里面找到最小的数值来替换（右树最左边的数据）
3.找到合适的数据之后，直接替换cur的值，然后删除那个合适的数据结点
else{
//找到合适的值（从右子树找最小值）
//target负责找到合适值，targetParent负责记录target的双亲结点
TreeNode targetParent = cur;
TreeNode target = cur;
while(target.left != null){
targetParent = target;
target = target.left;
}
cur.val = target.val;
//删除target，因为已经到最左边了，所以直接让parent的左边 = target的右边
//就算右边为空也没关系
targetParent.left = target.right;
}其实这个代码还存在一个问题，如下图，我们找到50为最小值进行替换，替换完删除50的时候执行targetParent.left = target.right; 但是变成20改为55了，这明显不对劲
也就是说，上面的代码只适合targetParent.left = target的情况
遇到这种targetParent.right = target的情况，需要让targetParent的右边 = target的右边
代码修改（只修改删除target的部分）
if(targetParent.left == target){
targetParent.left = target.right;
}else{
targetParent.right = target.right;
}不想看分析可以直接看这
整个的代码：
public void remove(int val){
TreeNode cur = root;
TreeNode parent = null;
while(cur!=null){
if(cur.val < val){
parent = cur;
cur = cur.right;
}else if(cur.val > val){
parent = cur;
cur = cur.left;
}else{
//开始删除
removeNode(cur,parent);
}
}
}
private void removeNode(TreeNode cur, TreeNode parent) {
if(cur.left == null){
if(cur == root){
root = parent.right;
}else if(cur == parent.left){
parent.right = cur.left;
}else{
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root){
root = parent.left;
}else if(cur == parent.left){
parent.left = cur.left;
}else{
parent.right = cur.left;
}
}else{
//找到合适的值（从右子树找最小值）
//target负责找到合适值，targetParent负责记录target的双亲结点
TreeNode targetParent = cur;
TreeNode target = cur;
while(target.left != null){
targetParent = target;
target = target.left;
}
cur.val = target.val;
//删除target
if(targetParent.left == target){
targetParent.left = target.right;
}else{
targetParent.right = target.right;
}
}
}Map的使用
搜索
我们学过的搜索
1.直接遍历: --> O(N)，速度较慢
2.二分查找：--> O(logN)，但要求搜索的序列有序
上面的搜索都属于静态搜索
而现实中我们需要在查找时进行一些插入和删除操作，就需要用到Map和Set这两个适合动态查找的容器了
Map属于Key-Value 模型 ， Key-Value 模型比如：统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数： < 单词，单词出现的次数 >梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
Map有两种形式，二叉搜索树和哈希表
Map<String,Integer> map = new TreeMap<>();//二叉搜索树, 查找复杂度O(logN)
Map<String,Integer> map1 = new HashMap<>();//哈希表, 查找复杂度O(1) 哈希表-->数组+列表+红黑树方法
put设置key和对应的value
get通过key来找到对应的值
如果找不到就返回null
getOrDefault方法和get差不多，只不过找不到就默认返回自己设置的返回值
keySet获取所有的key
entrySet返回key-value的所有关系
Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
而Set是所有Entry的集合
注意：
1.Map是一个接口，不能直接实例化对象，只能实例化其实现类TreeMap或HashMap
2.Map里的键值对中key是唯一的，但value是可以重复的，以最后一个value为准
3.Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
Set的使用
Set属于 纯 key 模型，纯 key 模型比如：有一个英文词典，快速查找一个单词是否在词典中快速查找某个名字在不在通讯录中
方法
iterator方法，输出每个key，每行1个
注意：
1.Set是继承自Collection的一个接口类
2.TreeSet的底层是TreeMap
3.实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
哈希表
概念
这种函数叫做哈希函数：hash(key) = key % capacity
capacity是存储元素底层空间的大小
哈希冲突：不同的关键字key，通过相同的哈希函数，得到相同的值
哈希冲突无法解决，只能降低冲突率
哈希函数的设计
合理的哈希函数可以降低冲突率
原则：
1.哈希函数定义域包括需要存储的全部关键码，如果散列表允许有m个地址时，值域必须在0到m-1之间
2.哈希函数计算出来的地址能均匀分布在整个空间中
3.哈希函数比较简单
常见的哈希函数
直接订制法：取关键字的某个线性函数为散列地址
public int firstUniqChar(String s) {
int[] count = new int[26];
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
count[ch-'a']++;
}
for(int i = 0; i< s.length();i++){
char ch = s.charAt(i);
if(count[ch-'a'] == 1){
return i;
}
}
return -1;
}除留余数法
负载因子调节
由图片我们可以知道负载因子越高，冲突率逐渐增加
填入表里面的元素已经是固定的情况下，为了使负载因子降低，我们只能让散列表扩容
冲突避免方法
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中还存在未填满的位置，那么可以把key存放到冲突位置的“下一个”空位置中去
那么怎么找到这个“下一个”位置呢？
1.线性探测法：
比如我们要在这个线性表中放入44，14，24，34，54
44与4冲突了，探测到4下一个的位置时空的，就把44放进去，后面的14，24，34挨个放进去空位置，到了54，后面没有位置可以放了，返回到前面继续探测，找到0位置
但是线性探测有个缺点，产生冲突的数据会堆在一块
2.二次探测
或者
H0时通过散列函数对关键码key计算出来的位置，m是表的大小，i = 0,1,2,3....代表的是要插入的数据排在第几位
这样明显不会堆在一起，而是均匀散开来了
开散列/哈希桶
又叫链地址法（开链法），采用数组+链表（+红黑树，当数组长度>64 && 链表长度 >=8 之后才会把链表变成红黑树）的方法，把冲突的元素采用尾插法插入被冲突元素的后面（JDK 1.7之前采用头插法，JDK 1.8之后采用尾插法）
数组的每个元素是链表的头节点
手搓一个哈希桶
初始化链表
每个结点需要有三个域，key,value和next
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;//记录存放的有效数据插入元素
第一步：首先用cur进行遍历，遍历index下标的链表是否存在key，如果存在就更新value，遍历完还不存在就插入元素
public void put(int key, int val){
int index = key % array.length;
//遍历index下标的链表是否存在key，如果存在就更新value，不存在就插入数据
Node cur = array[index];
while(cur!=null){
if(cur.key == key){
//更新value
cur.val = val;
}
cur = cur.next;
}
//cur==null-->遍历完没有找到key
// 头插法
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
usedSize++;
}第二步：计算负载因子
如果负载因子仍然大于默认的最低负载因子，则散列表需要进行扩容
public static final float DEFAULT_LOAD_FACTOR = 0.75f;
private float doLoadFactor(){
return usedSize * 1.0f / array.length;
}面试题：可以这样进行扩容吗？
if(doLoadFactor()>DEFAULT_LOAD_FACTOR){
//扩容
array = Arrays.copyOf(array, 2*array.length);
}都这么问了，那很明显是不行的😊
假设我们的11元素经过哈希之后放在插入到1下标这里
经过扩容之后，capacity发生了改变，变成了20
根据hash(key) = key % capacity，此时11%20 = 11
因为长度改变，原来冲突的元素放到了其他位置中去，所以这样扩容是不行滴
设置cur遍历原来的数组，每遍历到一个元素就纵向遍历链表的元素并进行头插法
代码：
注意：这里为什么要用一个tmp保存cur.next呢？
所以我们用一个tmp来保存原来的纵向遍历时11元素的地址
获取元素
public int get(int key){
int index = key % array.length;
Node cur = array[index];
while(cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;
}Map和Set其他一些注意事项
hashCode
创建一个student类，放入学生身份id
class Student {
public String id;
public Student(String id) {
this.id = id;
}
}
public class Test {
public static void main(String[] args) {
Student student1 = new Student("61012345");
Student student2 = new Student("61012345");
System.out.println(student1.hashCode());
System.out.println(student2.hashCode());
}
}我们发现打印出两种结果
在没有重写hashCode方法的时候，系统默认调取Object类里面的hashCode方法
虽然student1和student2的id属性值相同，但它们是不同的对象实例，因此它们在内存中有不同的地址。而Object里的hashCode使用对象的地址来生成哈希码，才有上面两种不同的结果
我们在student类里面重写一下方法（tips:可以点击generate-->equals() and hashCode()-->一路点下去创建方法）
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Student)) return false;
Student student = (Student) o;
return Objects.equals(id, student.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}重写完打印结果
这个结果才满足x%len=hashcode这个算式，x相同，len确定，得到的结果就是一样的
🆗接下来我们想要重新写一下上面的哈希桶代码，跟之前手搓的不一样的是，重写的方法允许key传入一个类实例化对象而不是单纯能进行比较大小的数字
泛型类哈希桶代码
public class HashBuck2 <K,V>{
static class Node<K,V>{
public K key;
public V val;
public Node<K,V> next;
public Node(K key, V val){
this.key = key;
this.val = val;
}
}
public Node<K,V>[] array;
public int usedSize;
public static final float DEFAULT_LOAD_FACTOR = 0.75f;
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;
Node<K,V> cur = array[index];
while(cur!=null){
//引用类型不能用等号
//if(cur.key == key){
if(cur.key.equals(key)){
//更新value
cur.val = val;
}
cur = cur.next;
}
Node<K,V> node = new Node(key,val);
node.next = array[index];
array[index] = node;
usedSize++;
}
public V getValue(K key){
int hash = key.hashCode();
int index = hash % array.length;
Node<K,V> cur = array[index];
while(cur != null){
if(cur.key.equals(key)){
return cur.val;
}
cur = cur.next;
}
return null;
}
}测试：
问题：hashCode和equals区别
一个例子带你看明白：
⚠以后在写自定义对象的时候建议把equals和hashCode重写一下
