数据结构《MapSet哈希表》

一、搜索树

1.1 定义

它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。

1.2 模拟实现搜索

public class MyBinarySearchTree {
    static class TreeNode{
        int key;
        TreeNode left;
        TreeNode right;
        public TreeNode(int key){
            this.key = key;
        }
    }
    private TreeNode root = null;


    /**
     * 查询节点
     * 查询是否有节点的key值为所需要找的，如果有返回这个节点，没有则返回null
     * @param key
     * @return TreeNode
     */
    public TreeNode search(int key){
        if(root == null){
            return null;//如果树为空，不用查询直接返回null
        }
        TreeNode cur = root;
        while (cur != null){
            if(key == cur.key){
                return cur;
            }else if(key < cur.key){//如果查询的值比节点的值小，说明只能在左子树上找
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }

        return null;
    }


    /**
     * 插入数据
     * 如果树为空直接插入，如果比节点的值大，往右边走，小，往左走，相等则不插入
     * @param key
     * @return
     */
    public boolean insert(int key){
        if(root == null){
            root = new TreeNode(key);
            return true;//树为空，直接插入并返回正确
        }
        TreeNode cur = root;
        TreeNode parent = null;//parent的存在，是为了让我们可以返回到上一个节点
        while (cur != null){
            if(key == cur.key){//如果要插入的数据已经存在，说明不需要插入
                return false;
            }else if(key < cur.key){//如果要插入的数据比节点值小，说明要往节点的左子树中插入
                parent = cur;
                cur = cur.left;
            }else {//如果要插入的数据比节点值大，说明要往节点的右子树中插入
                parent = cur;
                cur = cur.right;
            }
        }
        //到这里，说明我们cur已经为空，此时要插入的数据在parent的左子树或者右子树
        TreeNode treeNode = new TreeNode(key);
        if(key < parent.key){
            parent.left = treeNode;
        }else {
            parent.right = treeNode;
        }
        return true;
    }

    /**
     * 删除节点
     * 首先我们要找到这个删除的节点
     * @param key
     * @return
     */
    public boolean remove(int key){
        //首先要先找到这个点
        if(root == null){
            return false;//树为空无法删除
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }else if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }else {//说明找到这个点了
                return removeNode(parent,cur);
            }
        }

        return false;
    }

    /**
     * 删除节点的真正方法
     * @param parent
     * @param cur
     * @return
     */
    private boolean removeNode(TreeNode parent, TreeNode cur) {
        if(cur.left == null){//当要删除的节点左节点为空
            if(cur == root){//当节点为root时，那直接让root往右子树走即可
                root = cur.right;
            }else if(cur == parent.left){//节点不为root，说明cur为parent的左或者右孩子
                parent.left = cur.right;//因为cur左为空，所以父亲节点的左节点直接接上cur的右子树即可
            }else {
                parent.right = cur.right;
            }

        }else if(cur.right == null){//当要删除的节点右节点为空
            if(cur == root){//当节点为root时，那直接让root往左子树走即可
                root = cur.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {//当要删除的节点左右均不为空
            //找这个节点的左子树的最右边的节点或者右子树最左边的节点来替换数值
            TreeNode targetParent = cur;
            TreeNode target = cur.left;
            while (target.right != null){
                targetParent = target;
                target = target.right;
            }
            cur.key = target.key;
            targetParent.right = target.left;
        }

        return true;
    }


}

关于上述搜索树中其他的方法，比较简单，看代码大概可以了解如何实现，这里我们主要解释一下删除中的左右孩子节点都存在的情况下删除的原理


最后删除完的结果

测试用例

public class Test {
    public static void main(String[] args) {
        MyBinarySearchTree myBinarySearchTree = new MyBinarySearchTree();
        myBinarySearchTree.insert(5);
        myBinarySearchTree.insert(4);
        myBinarySearchTree.insert(6);
        myBinarySearchTree.insert(9);
        myBinarySearchTree.insert(3);
        myBinarySearchTree.insert(2);
        myBinarySearchTree.insert(7);
        myBinarySearchTree.insert(8);
        myBinarySearchTree.insert(10);
        MyBinarySearchTree.TreeNode treeNode = myBinarySearchTree.search(9);
        System.out.println(treeNode.key);
        System.out.println(myBinarySearchTree.remove(9));

    }
}

什么是键值对？
键（key）：它是独一无二的标识符，用于快速定位和检索对应的值。在一个Map集合里，不允许有两个相同的键，就像现实生活中每个人都有唯一的身份证号。常见的数据类型都能充当键，比如String、Integer，不过要求键对象必须正确重写hashCode()和equals()方法，以此保证唯一性和一致性。
值（value）：与键关联的数据，可以是任意类型，例如在统计单词出现次数的场景中，单词是键，出现的次数作为值，这个次数值就是Integer类型。一个键对应一个值，但不同键可以对应相同的值 。

二、Map

2.1 定义

Map是一个接口类，没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

注意：

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的key是唯一的，value是可以重复的
3. 在TreeMap中插入键值对时，key不能为空，否则会抛出NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。
4. Map中的key可以全部分离出来，存储到Set中来进行访问(因为key不能重复)。
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

2.2 Map.Entry

Map.Entry是一个接口，它表示Map接口中的一个键值对。每个实现了Map接口的类，例如HashMap、TreeMap等，内部都有对应的内部类实现了Map.Entry接口，用于封装单个的键值对元素，方便对Map进行遍历等操作。

如在HashMap中

在TreeMap中

2.3 TreeMap的使用

put(key, value):插入key-value的键值对
如果key不存在，会将key-value的键值对插入到map中,返回null
如果key之前是存过的，会将新的value值作为返回值返回，同时会将新的value值与之前的进行替换

Map<String,Integer> map = new TreeMap<>();
        //放入不同的人以及他的分数
        map.put("zhangsan",90);
        map.put("lisi",80);
        map.put("wangwu",88);
        Integer m = map.put("zhaoliu",92);
        Integer n = map.put("zhaoliu",99);
        System.out.println("m "+m);
        System.out.println("n "+n);

map.size()//返回map中已经存的键值对的个数

get()

		Map<String,Integer> map = new TreeMap<>();
        //放入不同的人以及他的分数
        map.put("zhangsan",90);
        map.put("lisi",80);
        map.put("wangwu",88);
        Integer m = map.put("zhaoliu",92);
        Integer n = map.put("zhaoliu",99);
		// get(key): 返回key所对应的value
        // 如果key存在，返回key所对应的value
        // 如果key不存在，返回null
        System.out.println(map.get("zhangsan"));
        System.out.println(map.get("wangmm"));

getOrDefault()

		//getOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println(map.getOrDefault("zhangsan", -100));
        System.out.println(map.getOrDefault("wangmm", -100));

containKey()

		//containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
        // 按照红黑树的性质来进行查找
        // 找到返回true，否则返回false
        System.out.println(map.containsKey("zhangsan"));
        System.out.println(map.containsKey("wangmm"));

containValue()

		// containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
        // 找到返回true，否则返回false
        System.out.println(map.containsValue(90));
        System.out.println(map.containsValue(100));

keySet()

返回类型: keySet()方法返回一个Set集合，因为Map中的键具有唯一性，所以用Set来存储很合适，Set集合会自动去除重复元素，保证每个键在集合里只出现一次。

遍历Map：获取到键的集合后，可以通过遍历这个Set，再配合Map的get方法，来遍历整个Map的键值对，这是一种常见的Map遍历方式。

		// 打印所有的key
		// keySet是将map中的key放入在Set中返回的
		for (String key : map.keySet()) {
            System.out.println(key + " : " + map.get(key));
        }

values()

		// 打印所有的value
        // values()是将map中的value放在collect的一个集合中返回的
        for(Integer integer : map.values()){
            System.out.print(integer + " ");
        }
        System.out.println();

entrySet()

		// 打印所有的键值对
        // entrySet(): 将Map中的键值对放在Set中返回了
        for(Map.Entry<String, Integer> entry : map.entrySet()){
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
        System.out.println();

2.4 Map的常用方法

三、Set

3.1 定义

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。

注意：

1. Set是继承自Collection的一个接口类

2. Set中只存储了key，并且要求key一定要唯一

3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
   
   
   

4. Set最大的功能就是对集合中的元素进行去重

5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入

7. TreeSet中不能插入null的key，HashSet可以。

3.2 TreeSet的使用

add()

TreeSet<String> treeSet = new TreeSet<>();

        // add(key): 如果key不存在，则插入，返回ture
        // 如果key存在，返回false
        treeSet.add("zhangsan");
        treeSet.add("lisi");
        treeSet.add("wangwu");
        boolean m = treeSet.add("zhaoliu");
        boolean n = treeSet.add("zhangsan");
        System.out.println(m);
        System.out.println(n);

size()

contains()

		// contains(key): 如果key存在，返回true，否则返回false
        System.out.println(treeSet.contains("zhangsan"));
        System.out.println(treeSet.contains("wangmm"));

3.3 Set的常用方法

四、哈希表

4.1 哈希表的概念

哈希表是一种数据结构，它使用哈希函数将键（Key）映射到存储桶（Bucket）或槽（Slot），以便可以在平均情况下以O(1)的时间复杂度进行快速的插入、删除和查找操作。

基本原理:

1. 哈希表由一个数组（也称为哈希表本身）和一个哈希函数组成。
2. 哈希函数：将键作为输入，通过某种计算得到一个整数索引，这个索引就是存储键值对的存储桶的位置。例如，对于键 k，哈希函数 h(k) 会计算出一个整数 i，表示键值对 (k, v) 应该存储在数组的第 i 个位置。
   

4.2 冲突

4.2.1 冲突的概念

当两个不同的键通过哈希函数计算得到相同的哈希值时，会发生哈希冲突。

在上面我们给出的例子中，没有出现冲突，如果通过例子中的hash函数，我们再放入一个数为44，那么我们就会和4冲突

4.2.2 冲突的避免

1. 选择合适的哈希函数

选择哈希函数的考虑因素：

1. 分布均匀性：
   理想的哈希函数应该将键均匀地分布在哈希表的存储桶中，避免大量冲突。
2. 计算速度：
   哈希函数的计算应该快速，避免复杂的计算，尤其是对于大量的插入、查找操作。
3. 抗碰撞性：
   对于安全相关的应用，需要更高的抗碰撞性，使用加密哈希函数；对于普通的哈希表，可能更注重速度和分布均匀性。

常用的函数：

1. 取模法: 对于一个整数键 k 和哈希表大小 m，哈希函数 h(k) = k % m
2. 直接定制法:取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

2. 负载因子调节

负载因子是哈希表中存储元素的数量与哈希表的容量（即存储桶的数量）的比值。
计算公式为：负载因子 = 元素数量 / 哈希表容量。

作用和意义:

1. 它是一个重要的性能指标，用于衡量哈希表的填充程度。
2. 在 Java 的 HashMap 中，负载因子决定了何时对哈希表进行扩容操作。
3. 合理的负载因子可以平衡空间使用和性能，避免过多的哈希冲突。

常见的负载因子取值：

1. 在 Java 的 HashMap 中，默认的负载因子是 0.75。
2. 当元素数量达到 哈希表容量 * 负载因子 时，HashMap 会自动扩容，通常扩容为原来的两倍，并重新哈希元素。

4.2.3冲突的解决

1. 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，可以把key存放到冲突位置中的下一个空位置中去。

1. 线性探测：如果发生冲突，顺序地检查下一个槽，直到找到一个空槽。
   采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
   

2. 二次探测（Quadratic Probing）：使用二次函数来确定下一个检查的槽，比如检查h(k) + 1^2 ，h(k) + 2^2，h(k) + 3^2，等等。

闭散列性能受探测序列和负载因子影响，当负载因子较高时，性能下降明显，空间利用率低。

2. 开散列

开散列法又叫链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化：

1. 每个桶的背后是另一个哈希表
2. 每个桶的背后是一棵搜索树

4.3 模拟实现

这里是我自己的一些理解，可能不是那么全面，如果有不对的地方，还望指正

节点的插入

数组的扩展

代码实现

public class HashTable<K,V> {
    private static final double DEFAULT_LOAD_FACTOR = 0.75f;
    static class Node<K,V>{
        public K key;
        public V value;
        public Node<K,V> next;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }
    //先定义一个数组来作为哈希表存放
    private Node<K,V>[] array = (Node<K,V>[])new Node[10];

    private int useSize = 0;


    public void push(K key,V value){
        int hashcode = key.hashCode();//获得哈希值
        int index = hashcode % array.length;
        Node<K,V> cur = array[index];
        while (cur != null){
            if(key.equals(cur.key)){//如果key在链表中存在，我们就更新它的value值，不新添节点，key唯一性
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node<K,V> node = new Node<>(key,value);
        node.next = array[index];
        array[index] = node;
        useSize++;
        if(doLoadFactor() > DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    private void resize() {
        Node<K,V>[] newarray = (Node<K,V>[])new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null){
                int newHashcode = cur.key.hashCode();
                int newIndex = newHashcode % newarray.length;//重新计算位置
                Node<K,V> curN = cur.next;//记录节点的下一个节点
                cur.next = newarray[newIndex];
                newarray[newIndex] = cur;
                cur = curN;
            }
        }
        array = newarray;
    }

    private double doLoadFactor() {
        return useSize * 1.0 / array.length;
    }

    public V getVal(K key){
        int hashcode = key.hashCode();
        int index = hashcode % array.length;
        Node<K,V> cur = array[index];
        while (cur != null){
            if(cur.key.equals(key)){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
}

当负载因子过大时，进行扩容

五、例题练习

例题1 字符串中的第一个唯一字符
通过HashMap来实现

class Solution {
    public int firstUniqChar(String s) {
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        for(int i = 0; i < s.length(); i++){
            if(map.get(s.charAt(i)) == 1){
                return i;
            }
        }
        return -1;

    }
}

例题2 只出现一次的数字

使用set

遍历数组，将数组中的数字放入set中，在放入之前判断set中是否存在这个数，如果存在，将set中的这个数出出去，最后遍历set中剩下的数便是出现一次的数

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
        }
        return 0;
    }
}

例题3 随机链表的复制

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);//key为老节点，value为新节点
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

例题4 宝石与石头
运用set存储宝石，然后看石头中在set中能不能找到

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        int count = 0;
        for(int i = 0; i < jewels.length(); i++){
            set.add(jewels.charAt(i));
        }
        for(int i = 0; i < stones.length(); i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }
}

例题5 旧键盘
将实际输入的字符串放入setReal中，然后从正确的字符串中一个一个取出字符看，实际输入的字符串中有没有，没有就打印并且将它放入已经判断后的set中，以防反复判断。

import java.util.Scanner;
import java.util.HashSet;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String strAct = in.nextLine();//正确的字符串
        String strBroken = in.nextLine();//实际输入的字符串
        strAct = strAct.toUpperCase();
        strBroken = strBroken.toUpperCase();
        HashSet<Character> hashSetReal = new HashSet<>();//实际输入的
        HashSet<Character> hashSetAlready = new HashSet<>();//已经判断过的
        for(int i = 0; i < strBroken.length(); i++){
            hashSetReal.add(strBroken.charAt(i));
        }
        for(int i = 0; i < strAct.length(); i++){
            char ch = strAct.charAt(i);
            if(!hashSetReal.contains(ch) && !hashSetAlready.contains(ch)){
                hashSetAlready.add(ch);
                System.out.print(ch);
            }
        }


    }
}

总结

本篇文章，介绍了有关Map和Set,以及哈希表相关的数据结构内容，如果有什么不正确不严谨的地方，还望指正，我会尽快更改，谢谢大家！！