数据结构专栏
如烟花般绚烂却又稍纵即逝的个人主页
本章讲述数据结构中搜索二叉树与HashMap的学习，感谢大家的支持！欢迎大家踊跃评论，感谢大佬们的支持!
目录
- 搜索二叉树的概念
- 二叉树搜索模拟实现
- 搜索二叉树查找
- 搜索二叉树插入
- 搜索二叉树删除
- HashMap 和HashSet的定义
- hashCode（开散链法）
- 哈希冲突
- 模拟实现哈希桶（尾叉法）
- 模拟创建泛型哈希桶
搜索二叉树的概念
二叉树左边的值小与根节点，右边的值大于根节点。
左树<根节点<右树
这样也大大提升了我们代码搜索的效率
这时通过中序遍历得到一个有序的数组。
二叉树搜索模拟实现
搜索二叉树查找
给一个值来判断数组中是否包含这个元素。
思想:1.节点不能为空，为空说明没有元素
2.明确左边的数都比跟节点要小，而右边的树比跟节点大，小往左走，大往右走，搜索到返回true，出了条件返回false（没有搜索到此元素）。
public boolean search(int val){
TreeNode cur=this.root;
while(cur!=null){
if(val>cur.val){
cur=cur.right;
}else if(val<cur.val){
cur=cur.left;
}else{
return true;
}
}
return false;
}
时间复杂度:最好情况下O(logN)
最坏情况下O(N)——在单分枝的情况下
搜索二叉树插入
如果要插入数据的情况下，插入的数据大于根节点一直走，如果小于根节点则插入左树，如果一直大于则直到为空插入，因为遍历的cur为空出来后没有最后一个节点的位置，在插入之前需要定义一个parent来记录根节点的，来放到左树或者右树。
public boolean insert(int val){
if(this.root==null){
//root为空情况下
this.root=new TreeNode(val);
return true;
}
TreeNode cur=this.root;
//定义一个值来接收前一个父亲节点值
TreeNode parent=null;
while(cur!=null){
parent=cur;
if(cur.val>val){
parent=cur;
cur=cur.left;
} else if (cur.val< val) {
parent=cur;
cur=cur.right;
}else{
//不需两个相同元素存在
return false;
}
}
TreeNode node=new TreeNode(val);
if(parent.val>val){
//插入左边
parent.left=node;
}else{
parent.right=node;
}
return true;
}
搜索二叉树删除
当我们要删除树中某一个节点的时候我们要考虑的情况比较多当left为空节点.
这里分三种情况讨论
第一种情况：
1.如果想要删除的节点为root，且左树为空情况下，则直接指向right。
因为parent事cur的上一个节点的记录
2.如果parent的左树为cur且cur的左树为空，则parent.left=cur.right。
3.如果parent的右树是cur且cur的左树为空，则parent.right=cur.right。
第二种情况：
1当cur==root时且没有右树，则左树为新的根节点。
2.parent指向的左树为cur时，因为cur没有右树则parent.left=cur.left。
3.parent指向的右树为cur时，因cur没有右树则parent.right=cur.left。
第三种情况：要删除的cur的左右子树都不为空。
如果都不为空，需要找到比左树大，但是比右树要小的值。
如果cur的下一个右树节点的左树存在最小值则直接将其cur覆盖。或者cur的右树没有左树节点，则右树第一个节点覆盖掉cur。
cur的左右树都不为空，则cur是比左树要到，所以不需要考虑cur的左树部分。
定义两个值来标记targetParent和target的右树，从右树的左侧找到最小值，进行覆盖（curParent来作为上一个的父亲节点），这时候要删除target节点，当targetParent的左树为target时，因为target一定是在最后一个左树位置，target的右树赋值给targetParent来取消与target的连接。
如果target为右树则targetParent直接指向target的下一个右树。
public void removeThisNode(TreeNode cur,TreeNode parent){
if(cur.left==null){
//如果cur根节点为要删除的节点，直接将root指向cur.right
if(cur==this.root){
this.root=cur.right;
} else if (cur==parent.left) {
parent.left=cur.right;
}else{
parent.right=cur.right;
}
} else if (cur.right==null) {
if(cur==root){
this.root=cur.left;
} else if (cur==parent.left) {
parent.left=cur.left;
}else{
parent.right=cur.left;
}
}else{
TreeNode targetParent=cur;
TreeNode target=cur.right;
while(target.left!=null){
targetParent=target;
target=target.left;
}
//cur的值被target覆盖掉
cur.val=target.val;
//这里target的指向修改
if(targetParent.left==target){
targetParent.left=target.right;
}else{
targetParent.right=target.right;
}
}
}
时间复杂度O(logN)
HashMap 和HashSet的定义
HashSet是java集合框架中Set的常用类。
HashSet不允许存储重复元素的集合，它使用哈希表来存储元素（val），确保每一个元素是唯一的，时间复杂度为O(1).
HashMap是java集合框架Map的常用类。
HashMap也是用哈希表通过key键值来存储val，与HashMap不同，它通过key键值来存储，元素可以相同，但是key键值一单相同val值就会被覆盖掉。
hashCode（开散链法）
二叉搜索树是通过对半切的方式进行比较，类似于我们的二分法查找，但是它的如果是两边的树是平衡时，时间复杂度是O(logN),如果是一棵单分枝树时间复杂度来到O(N)都要进行遍历。
而哈希可以不经过比较，一次性从想要查找的范围内获取到该元素。
如果想要实现，通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，通过公式：hash=key（查找的下标）%capacity（容量）如下图所示：
5%10=5将19到5下标
13%10=3将24放到3下标
15%10=5将52放到5下标的链表的next处
哈希冲突
而通过上述我们发现，5，15都已经放到了5下标位置，不同关键字通过相同的哈希函数计算出相同的哈希地址
如何避免哈希冲突？
哈希冲突无法直接避免，因为key我们的元素是不能改变的，我们只能控制空间的大小，来减少链表中元素
负载因子 = 表中有效数据个数 / 空间的大小。
>负载因子越大，产出冲突的概率越高，增删查改的效率越低。
负载因子越小，产出冲突的概率越低，增删查改的效率越高。
负载因子设定为0.75
当我们的元素个数/空间的长度如果超出0.75，则需要扩容，加大空间，将负载因子缩小，从而让查改效率加强。
模拟实现哈希桶（尾叉法）
1.这里我们创建一个哈希表来进行搜索，通过数组和链表的方式来构成，让其更快搜索到想要搜索到的值，将下标值放入指定的数组链表中来存储。
2.每个数组的下标对应一个链表，当想要搜索某个下标值时，hash=key%capacity 得到的就是某一下标的链表，通过链表连接该key的每一个元素。
3.判断是否需要大于负载因子（扩容 ）
当我们扩容时，通过2*len的长度进行扩容，然后通过key%新定义的数组的容量，给到新的数组链表中，将之前存储的链表指向其他下一个节点即可。
public class HashBucket {
//内部类
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;
int size;//长度
public static final float loadFactor=0.75f;//负载因子的默认值
public HashBucket(){
//构造方法
this.array=new Node[10];
}
//放入元素
public void put(int key,int val){
int index=key%array.length;
Node node=new Node(key,val);
Node preV=null;
//为空
if(this.array[index]==null){
this.array[index]=node;
}else{
//不为空
Node cur=this.array[index];
while(cur!=null){
if(cur.key==key){
cur.val=val;
return;
}
preV=cur;
cur=cur.next;
}
assert preV!=null;
preV.next=node;
}
size++;
if(judgThisLoadFactorFull())
//扩容
grow();
}
//判断是否大于负载因子
public boolean judgThisLoadFactorFull(){
return size*1.0f/array.length>loadFactor;
}
//扩容
private void grow() {
Node[] newArray=new Node[2*array.length];//两倍的扩容
for(int i=0;i<array.length;i++){
Node cur=this.array[i];
Node preV=null;
while(cur!=null){
int index= cur.key%newArray.length;
if(newArray[index]==null){
newArray[index]=cur;
cur=cur.next;
this.array[i]=cur;
newArray[index].next=null;
}else{
Node newCur=newArray[index];
while(newCur!=null){
preV=newCur;
newCur=newCur.next;
}
assert preV!=null;
preV.next=cur;
cur=cur.next;
this.array[i]=cur;
preV.next.next=null;
}
}
}
this.array=newArray;
}
//通过key搜索到值
public int getValByThisKey(int key){
int index=key%this.array.length;
Node cur=this.array[index];
while (cur!=null){
if(cur.key==key){
return cur.val;
}
cur=cur.next;
}
return -1;
}
当我们创建了一个泛型的类型后，生成了hashCode方法，我们生成两个参数相同的对象时，如果将student1放入到hashmap中，当我们想要查找hashmap1中的值时，使用student2也可以查到student1中的值，这里的哈希函数通过计算关键码，因为两者的关键码相同，得到关键码的数值。
Student student1=new Student("12313");
Student student2=new Student("12313");
System.out.println(student1.hashCode());
System.out.println(student2.hashCode());
HashMap<Student,Integer> hashMap=new HashMap<>();
hashMap.put(student1,2);
System.out.println(hashMap.get(student2));
而我们如何自己模拟实现一个自定义类型的哈希桶呢？
接下来我们实现以下
模拟创建泛型哈希桶
这里泛类型哈希桶实现与上述哈希桶实现类似，但是这里注意get方法中的比较关键码是通过equals来判断。
public class HashBucket<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 DefaultFactor=0.75f;
public HashBucket(){
this.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];
Node<K,V> node=new Node<>(key,val);
Node<K,V> preV=null;
if(cur==null){
this.array[index]=node;
}else{
while(cur!=null){
if(cur.key==key){
cur.val=val;
}
preV=cur;
cur=cur.next;
}
preV.next=node;
}
usedSize++;
}
//获取值
public V get(K key){
int hash= key.hashCode();
int index=hash % array.length;
Node<K,V> cur=this.array[index];
while(cur!=null){
//这里比较不是==
if(cur.key.equals(key)){
return cur.val;
}
cur=cur.next;
}
return null;
}
}
