❣博主主页: 33的博客❣
▶️文章专栏分类:数据结构◀️
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识
目录
- 1.前言
- 2.搜索树
- 2.1 概念
- 2.2实现二叉搜索树
- 2.4性能分析
- 3.搜索
- 3.Map
- 3.1Map说明
- 3.2 Map 的常用方法说明
- 4.set
- 5.哈希表
- 5.1 概念
- 5.2冲突
- 5.3冲突-避免-负载因子调节
- 5.4 冲突-解决-开散列/哈希桶
- 5.4.1哈希桶的实现
- 6.总结
1.前言
本篇文章将讲解数据结构的最后一个集合类：Map和Set。希望同学们能掌握 Map/Set 实际实现类 HashMap/TreeMap/HashSet/TreeSet 的使用以及背后的数据结构哈希表的原理和简单实现。
2.搜索树
2.1 概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
2.2实现二叉搜索树
定义节点
static class TreeNode{
int val;
TreeNode right;
TreeNode left;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root;
查找元素
//查找某个元素
public boolean search(int key) {
//搜索树为空
if(root==null){
return false;
}
//根节点等于key
if(root.val==key){
return true;
}
TreeNode cur=root;
//不为空，且根节点！=key
while (cur!=null){
if(cur.val<key){
cur=cur.right;
}else if (cur.val>key){
cur=cur.left;
}else {
//cur.val=key;
return true;
}
}
return false;
}
插入元素：
1.如果为空，那么直接插入
2.不为空，如果小于根则插入左边，大于则插入右边
//插入元素
public boolean insert(int val) {
TreeNode key=new TreeNode(val);
if (root==null){
root=key;
return true;
}else {
TreeNode node=root;
TreeNode parent=null;
while (node!=null){
if(node.val>val){
parent=node;
node=node.left;
}else if (node.val<val){
parent=node;
node=node.right;
}else {
//相等
return false;
}
}
node=key;
if(parent.val>val){
parent.left=node;
}else {
parent.right=node;
}
}
return true;
}
删除元素：
设待删除结点为 cur, 待删除结点的双亲结点为 parent
- cur.left == null
cur 是 root，则 root = cur.right
cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
cur 不是 root，cur 是 parent.right，则 parent.right = cur.right - cur.right == null
cur 是 root，则 root = cur.left
cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
cur 不是 root，cur 是 parent.right，则 parent.right = cur.left - cur.left != null && cur.right != null
需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题
//删除元素
public void remove(int key) {
//找到key这个节点的位置
if(root==null||root.val==key){
return ;
}
TreeNode cur=root;
TreeNode parent=null;
//不为空，且根节点！=key
while (cur!=null){
if(cur.val<key){
parent=cur;
cur=cur.right;
}else if (cur.val>key){
parent=cur;
cur=cur.left;
}else {
//cur.val=key;
removekey(cur,parent);
}
}
}
public void removekey(TreeNode cur,TreeNode parent){
if(cur.left==null){
if(cur==root){
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) {
root = cur.left;
} else if (cur == parent.left) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
}else {
//cur.left！=null&&cur.right!=null,
//那么就在cur的左边找到最大值，或者cur的右边找到最小值来替换该元素
TreeNode node=cur;
parent=cur;
cur=cur.right;
while (cur.left!=null){
parent=cur;
cur=cur.left;
}
node.val=cur.val;
//删除替代元素
if(parent.left==cur){
parent.left=cur.right;
}else {
parent.right=cur.right;
}
}
}
}
2.4性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：
l
o
g
2
n
log_2^n
log2n
最差情况下，二叉搜索树退化为单支树，其平均比较次N数为：N
3.搜索
Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。
一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以
模型会有两种：
- 纯 key 模型，比如：
有一个英文词典，快速查找一个单词是否在词典中
快速查找某个名字在不在通讯录中- Key-Value 模型，比如：
统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对，Set中只存储了Key。
3.Map
3.1Map说明
从上图我们可以看出,Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。
Map.Entry<K, V>
Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取：getKey（），getValue和value的设置：setValue以及Key的比较方式。
3.2 Map 的常用方法说明
注意
- Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
- Map中存放键值对的Key是唯一的，value是可以重复的
- 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但
是HashMap的key和value都可以为空。 - Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
- Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
- Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行
重新插入。
TreeMap和HashMap的区别
4.set
Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。
注意
- Set是继承自Collection的一个接口类
- Set中只存储了key，并且要求key一定要唯一
- TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
- Set最大的功能就是对集合中的元素进行去重
- 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础
上维护了一个双向链表来记录元素的插入次序。- Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
- TreeSet中不能插入null的key，HashSet可以。
5.哈希表
5.1 概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(
l
o
g
2
n
log_2^n
log2n )，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为*：hash(key) = key % capacity*; capacity为存储元素底层空间总的大小。
5.2冲突
例如：数据集合{1，7，6，4，5，9，11}，假设capacity=10
hash(1) =1 % 10=1，hash(11) =11 % 10=1
我们发现：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。但是冲突的发生是必然的，我们只能做到尽量避免冲突。
5.3冲突-避免-负载因子调节
负载因子和冲突率的关系粗略演示：
已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。
5.4 冲突-解决-开散列/哈希桶
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
5.4.1哈希桶的实现
public class MyHashBuck {
//每个节点
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[] arr;
public int useSize;
public static final float DEFAULT_LOAD_FACTOR = 0.75f;
public MyHashBuck() {
arr = new Node[10];
}
//加入方法
public void put(int key,int val) {
int index=key%arr.length;
Node cur=arr[index];
while (cur!=null){
if(cur.key==key){
cur.val=val;
return;
}
cur=cur.next;
}
//遍历完成都没有相同的元素，那么就头插
Node node=new Node(key,val);
node.next=arr[index];
arr[index]=node;
useSize++;
if(useSize*1.0f / arr.length>DEFAULT_LOAD_FACTOR){
//负载因子大于0.75就扩容
//array = Arrays.copyOf(array,2*array.length);不能这样写，因为扩容后11可能就不在1的位置，而在11的位置，所以要重新求位置
resize();
}
}
//重哈希
public void resize() {
Node[] newarr=new Node[2*arr.length];
for (int i=0;i<arr.length;i++){
Node cur=arr[i];
while (cur!=null){
Node tmp=cur;
int newindex=cur.key/newarr.length;
cur.next=newarr[newindex];
cur=tmp.next;
}
}
arr=newarr;
}
//获取val
public int get(int key) {
int index=key%arr.length;
Node cur=arr[index];
while (cur!=null){
if(cur.key==key){
return cur.val;
}
cur=cur.next;
}
return -1;
}
}
6.总结
本篇文章将讲解数据结构的最后一个集合类：Map和Set。希望同学们能掌握 Map/Set 实际实现类HashMap/TreeMap/HashSet/TreeSet 的使用以及背后的数据结构哈希表的原理和简单实现。
