寸_铁

这个屌丝很懒，什么也没留下！

热门标签

数据结构之Map和Set（下）

作者：寸_铁 | 2024-08-16 05:03:28

踩

数据结构之Map和Set（下）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

上一篇文章，我们学习了：二叉搜索树、Map和Set的介绍以及常见方法的基本使用、哈希表的相关内容：冲突、冲突的避免。数据结构之Map与Set（上）-CSDN博客

接下来，我们就来学习剩下的有关知识。

冲突-解决-闭散列

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

1.线性探测

比如上面的场景，现在需要插入元素44，先通过哈希函数 (插入的元素 % 散列表的长度) 计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

通过哈希函数获取待插入元素在哈希表中的位置。如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。如上图中的8下标位置。如下图所示：

注意：

采用闭散列处理哈希冲突时，不能随便进行物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。例如：用节点来表示一个一个的元素，而节点中有一个布尔类型的变量来表示这个元素是否存在即可。

2.二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，如果找到了就插入元素，否则就继续往后找。如果要插入的元素算出其下标都为此，那么元素就会堆积在一起。因此二次探测为了避免该问题，找下一个空位置的方法为：H=(Ho+i²)% m,或者：H= (Ho- 2² )% m。其中：i= 1,2,3..， Ho是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置（即原来要存放的位置），m是表的大小。对于上图如果要插入44，产生冲突，使用解决后的情况为：

H=(Ho+i²)% m ---> H = (4 + 1^2) % 10 = 5 ---> 这个位置已经有了元素，继续往后找；

H=(Ho+i²)% m ---> H = (4 + 2^2) % 10 = 8 ---> 这个位置没有元素，就插入元素。

注意：

研究表明：当表的长度为质数且表装载因子（负载因子）a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。那么这样就会造成严重的空间浪费，这就是所谓的空间换时间的做法。

冲突-解决-开散列/哈希桶

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。其实就是一个数组加多个单链表。如下图所示：

这样，即使产生了冲突，我们也可以存放到相同的下标。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。那么又有一个新问题来了：如果这个单链表很长，那么搜索的时候，时间复杂度不就变成O(N)了吗？没错的确是这样，因此为了避免这种情况（单链表的长度很长）就有了新的办法：每个数组元素又是一个新的哈希表，而每个单链表转换为一棵搜索树。

手动实现哈希表

思路：其实就是实现一个数组和多个单链表的增加、修改、查找。

准备代码：


    // 节点
    private static class Node {
        private int key;
        private int value;
        public Node next;
 
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
 
    private Node[]  array;
    private int size; // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75; // 负载因子
    private static final int DEFAULT_SIZE = 8; // 默认桶的大小（单链表的长度）
 
    // 哈希表的构造方法
    public HashBucket() {
        array = new Node[DEFAULT_SIZE];
    }
 
    // 获取负载因子
    private double loadFactor() {
        return size * 1.0 / array.length;
    }

增加 / 修改元素：

思路：通过哈希函数计算出下标找到要插入位置，进行头插法即可。

代码实现：


    public int put(int key, int value) {
        int index = key % array.length;
        // 首先得判断哈希表中是否有这个节点，有就更新value值即可
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return value;
            }
            cur = cur.next;
        }
        // 如果实际的负载因子大于默认负载因子就得扩容
        if (loadFactor() >= LOAD_FACTOR) {
            resize();
        }
        // 采用头插的方式来创建单链表
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;
        size++;
        return value;
    }

扩容哈希表：

思路：申请一个比原数组大一倍的，然后遍历原数组，重新寻找要合适的位置进行插入元素。

代码实现：


    private void resize() {
        // 注意不能直接2倍扩容，因为扩容之后的元素位置可能会发生改变
        // array = Arrays.copyOf(array, 2*array.length);
 
        // 申请一个新的数组，遍历原数组来插入元素
        Node[] newArray = new Node[2*array.length];
        // 注意这里不能是size，因为不一定是从0下标开始存放的
        for (int i = 0; i < array.length; i++) {
            // 遍历单链表
            Node cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;
                Node node = new Node(cur.key, cur.value);
                node.next = newArray[index];
                newArray[index] = node;
                cur = cur.next;
            }
        }
        array = newArray;
    }

一定要注意：

1、不能直接两倍扩容。因为有的元素不一定在合适的位置；

2、不能把遍历的截止条件写成 size。因为 size 只是记录了不同元素的个数，而不一定会包括全部的元素在内。

查找元素：

思路：直接遍历就完了。

代码实现：


    public int get(int key) {
        Node cur = array[key % array.length];
        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入 / 删除 / 查找的时间复杂度是 O(1) 。

哈希表和Java类的关系

1、HashMap 和 HashSet 即 Java 中利用哈希表实现的 Map 和 Set。
2、Java 中使用的是哈希桶方式解决冲突的。
3、Java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树 (红黑树)。这个值是 8，并且哈希表的长度要大于等于64，这两个条件同时满足。
4、Java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashcode 和 equals 方法，而且要做到 equals 相等的对象，hashcode 一定是一致的。

有关Map和Set的相关练习

136.只出现一次的数字

题目：

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。

思路一：最简单、最有效的做法就是采用异或的方法，异或的规则是：（二进制位）相同为0，相异为1，因此剩下的单身狗就能被找出来。

代码实现：


class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }
}

思路二：利用去重的思想：如果没有这个元素，就插入元素；否则，就删除元素。这里可以随便用一个我们学过的数据结构来写，例如：顺序表、链表、栈、队列 ..... 这里我们采用Set来解决。

代码实现：


class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        Iterator<Integer> iterator = set.iterator();
        // 因为只有一个元素，因此一次遍历即可找到（Set中没有get方法）
        if (iterator.hasNext()) {
            return iterator.next();
        }
        return -1;
    }
}

138.随机链表的复制

题目：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

思路一：采用哈希表的方式。哈希表key与value的对应关系就类似原链表和新链表的关系一一对应。

代码实现：


class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        // 把原链表和新链表的对应关系建立
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        // 更新新链表的next值和random值
        cur = head;
        while (cur != null) {
            // 注意：下面的代码是不符合要求的（是浅拷贝）
            // map.get(cur).next = cur.next;
            // map.get(cur).random = cur.random;
 
            // 是要修改新链表的next和random指向新链表的节点，而不是原链表的节点
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

思路二：采用传统的创建链表的方式。这种方法属于大佬才能想到。在原链表的基础上，构建出新的链表：原链表节点1号--->新链表节点1号--->原链表节点2号--->新链表节点2号--->原链表节点3号--->新链表节点3号--->......这样就构建出了next值，再次遍历原链表（此时变成了拼接链表），更新random指向，最后再遍历拼接链表分割成两个不同的链表。

注意：这里不能同时构建拼接链表的同时来更新random值，因为新链表random值指向的节点还没有创建。

代码实现：


class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 创建新链表
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            // 添加在原链表的节点后面
            tmp.next = cur.next;
            cur.next = tmp;
            // 此时得跳过两个节点，才能到达原链表的下一个位置
            cur = cur.next.next;
        }
        // 添加随机指针
        cur = head;
        // cur不为null，也就意味着cur.next也不为null了
        // cur和cur.next是一样对应的。因此不必判断cur.next是否为null
        while (cur != null) { 
            if (cur.random != null) {
                // 这里一定要是cur.random.next（代表是新链表的节点，而不是原链表）
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 断裂原链表
        cur = head;
        Node newHead = cur.next;
        Node newCur = newHead;
        while (cur != null && cur.next != null) {
            // 在进行判断的时候，会把原链表与新链表进行比对
            // 因此，原链表不能改变，但是我们之前改变了原链表，因此得修改回来
 
            // 下面代码的处理方式很巧妙
            cur.next = cur.next.next; // 跳着把链表链接了           
            newCur.next = newCur.next == null ? null : newCur.next.next;
            cur = cur.next;
            newCur = newCur.next;
        }
        return newHead;
    }
}

总结：如果不用哈希表的方法去做的话，难度瞬间就上来了：首先得知道怎么处理，其次细节要注意的地方也比较多。

771.宝石与石头

题目：

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

示例 1：
输入：jewels = "aA", stones = "aAAbbbb"
输出：3
示例 2：
输入：jewels = "z", stones = "ZZ"
输出：0
提示：

1 <= jewels.length, stones.length <= 50
jewels 和 stones 仅由英文字母组成
jewels 中的所有字符都是 唯一的

思路一：直接双层遍历，外层遍历宝石，内层遍历石头，记录有多少宝石即可。

思路二：直接用Set把宝石记录下来，再去遍历石头，记录有多少宝石即可。

代码实现：


class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        // 把宝石放到Set中，遍历石头看看是否包含宝石
        Set<Character> set = new TreeSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            // 因为jewels中字符是唯一的
            set.add(jewels.charAt(i));
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }
}

692.前K个高频单词

题目：

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。
注意：

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]

思路：遍历数组统计每个单词出现的次数，再建立小根堆来存放前k个元素，最后再将堆中元素全部插入List中，最后再逆序即可。

代码实现：


class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> list = new ArrayList<>(k);
        // 统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (map.get(words[i]) == null) {
                map.put(words[i], 1);
            } else {
                // 更新出现的次数
                int val = map.get(words[i]);
                map.put(words[i], val+1);
            }
        }
        // 创建小根堆，并且添加符合题目要求的元素
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                // 如果频率一样，就比较字典顺序
                if (o1.getValue().compareTo(o2.getValue()) != 0) {
                    return o1.getValue().compareTo(o2.getValue());
                } else {
                    return o2.getKey().compareTo(o1.getKey());
                }
            }
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()){
            // 如果小根堆的个数小于k个时，就直接进行插入即可
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                // 开始进行比较
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    // 出现频率不符合
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0
                        && top.getKey().compareTo(entry.getKey()) > 0) {
                    // 出现的频率一样但不符合字典顺序
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }
        // 开始存放到list中
        while (!minHeap.isEmpty()) {
            Map.Entry<String, Integer> entry = minHeap.poll();
            list.add(entry.getKey()); // 从小到大存放的
        }
        Collections.reverse(list);
        return list;
    }
}

注意：在比较字典顺序时，一定要是 o2.getKey().compareTo(o1.getKey())。如下图所示：

因此，当单词出现的频率一样时，要根据字典顺序建立大根堆。

注意：Arrays 是操作数组的类；Collections 是操作集合的类。

好啦！本期数据结构之Map和Set（下）的学习之旅到此结束啦！我们下一期再一起学习吧！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/986701