Java数据结构第二十三期：Map与Set的高效应用之道(二)

专栏：Java数据结构秘籍

个人主页：手握风云

目录

一、哈希表

1.1. 概念

1.2. 冲突

1.3. 避免冲突

1.4. 解决冲突

1.5. 实现

二、OJ练习

2.1. 只出现一次的数字

2.2. 随机链表的复制

 2.3. 宝石与石头

---

一、哈希表

1.1. 概念

        顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找⼀个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为，平衡树中为树的⾼度，即，搜索的效率取决于搜索过程中元素的比较次数。

        理想的搜索⽅法：可以不经过任何比较，⼀次直接从表中得到要搜索的元素。如果构造⼀种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

        当向该结构中，根据待插⼊元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。该方式即为哈希(散列)方法，哈希方法中使⽤的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

        哈希函数设置为：hash(key) = key % capacity；其中capacity为存储元素底层空间总的大小。

        我们设一个整数集合{1,7,6,4,5,9}，把capacity设置为10，那我们就可以按照下图来存储。如果我们再想存放一个元素12，我们可以直接通过哈希函数存进下标2中，要想搜索，直接通过2下标来找到12，这样时间复杂度为，从而提高效率。

1.2. 冲突

        不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码⽽具有相同哈希地址的数据元素称为“同义词”。例如我们要想存放一个14，通过上面的哈希函数应该存到4下标，但此时4下标已经存了一个4，就会造成哈希冲突。

        出现了哈希冲突，我们就要想办法避免冲突。由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，就会导致冲突的发⽣是必然的，但我们能做的应该是尽量的降低冲突率。

1.3. 避免冲突

        第一种方法可以设计合理的哈希函数。设计原则：定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间；计算出来的地址能均匀分布在整个空间中；比较简单。

        直接订制法：取关键字的某个线性函数为散列地址：Hash(Key) = A*Key + B。优点：简单、均匀。缺点：需要事先知道关键字的分布情况。使用场景：适合查找比较小且连续的情况。

        除留余数法：设散列表中允许的地址数为m，取⼀个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。

        哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

        我们还有另外一种就是调节负载因子。哈希表的载荷因子为：ą=填入表中元素个数/哈希表长度。当冲突率达到⼀个⽆法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

1.4. 解决冲突

        解决哈希冲突两种常⻅的⽅法是：闭散列和开散列。

        闭散列：也叫开放地址法，当发⽣哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下⼀个” 空位置中去。那如何寻找下⼀个空位置呢？此时我们就需要应用线性探索。从发生冲突的位置开始，依次向后探测，直到寻找到下⼀个空位置为止。但这样还是会有一个缺点，就是会使得冲突元素聚集在一起，并且如果我们把4删除了，又如何寻找14、24、34这些元素。因此线性探测采⽤标记的伪删除法来删除⼀个元素。

        ⼆次探测为了避免该问题，找下⼀个空位置的⽅法为：Hi = (H0+i^2)%m，i表示冲突的次数，m为表的大小。

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

1.5. 实现

        由于我们需要节点数组来创建哈希表，利用内部类来表示节点对象。

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 = new Node[10];public int UsedSize;//表示还系统中存放的元素public static final float LOAD_FACTOR = 0.75f;//负载因子表示为常数
}

        我们先来模拟哈希表中放元素的方法。我们要想把元素放入，首先得是一个结点。比如key=14，如果表中已经有14了，就不能再放14并且更新val，所以我们首先需要遍历数组判断key是否相同，如果相同，更新val。下面再使用头插法来把节点元素放入哈希表中。插入元素之后，我们还需要重新计算负载因子是否超过了我们规定的LOAD_FACTOR。如果超过了，就需要进行扩容操作。扩容的时候还需要注意，比如我们要插入的元素的key为14，扩容前需要插入下标为4的位置，扩容2倍后，就需要插入下标为14的位置。

        完整代码实现：

    public void put(int key, int val) {int index = key % array.length;//先遍历index数组下的链表，如果有相同的key，则更新valNode cur = array[index];while (cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}//头插法Node node = new Node(key, val);node.next = array[index];array[index] = node;UsedSize++;//重新计算负载因子是不是超过了我们规定的值if (CalculateLoadFactor() >= LOAD_FACTOR) {//扩容ReSize();}}private float CalculateLoadFactor() {return UsedSize * 1.0f / array.length;}private void ReSize() {Node[] newArray = new Node[array.length*2];for (Node node : array) {Node cur = node;while (cur != null) {int newIndex = cur.key % newArray.length;//把当前节点放入新数组的位置,再次使用头插法Node curNext = cur.next;cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = curNext;}}array = newArray;}

        get方法也是一样，也是通过索引下标来寻找目标值。

    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;}

        我们在Test类里面进行实例化并调试。

public class Test {public static void main(String[] args) {HashBucket hashBucket = new HashBucket();hashBucket.put(11,99);hashBucket.put(2,99);hashBucket.put(43,99);hashBucket.put(4,99);hashBucket.put(14,99);hashBucket.put(24,99);hashBucket.put(7,99);hashBucket.put(8,99);}
}

        我们上面的方法key是整型，那如果key是引用类型呢，比如String或者Person类。那我们就把整型换作是泛型K、V。需要注意的是，key换成了泛型，不能直接进行%操作，我们可以使用hashCode方法转成整型，并且进行比较要使用equals方法。

/*** @author: gao* @create-date: 2025/3/15 16:32*/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 = (Node<K, V>[]) new Node[10];public int UsedSize;//表示还系统中存放的元素public static final float LOAD_FACTOR = 0.75f;//负载因子表示为常数public void put(K key, V val) {int hashcode = key.hashCode();int index = hashcode % array.length;//先遍历index数组下的链表，如果有相同的key，则更新valNode<K, V> cur = array[index];while (cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}Node<K, V> node = new Node<K, V>(key, val);node.next = array[index];array[index] = node;UsedSize++;}public V get(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.val;}cur = cur.next;}return null;}
}

        如果我们要判断是否为同一个人，我们可以判断身份证号码是否相等。如果我们按照这种方法去写，发现比较结果为false。这是因为我们没有重写equals和hashCode方法，编译器默认调用Object方法。

class Person {public String id;public Person(String id) {this.id = id;}
}public class Test {public static void main(String[] args) {Person person1 = new Person("1234");Person person2 = new Person("1234");System.out.println(person1.equals(person2));System.out.println(person1.hashCode());System.out.println(person2.hashCode());}
}

    public boolean equals(Object obj) {return (this == obj);}

        我们在Person类里面右击，点击Generate，再点击equals() and hashCode()，就可以重写。

    @Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return Objects.equals(id, person.id);}@Overridepublic int hashCode() {return Objects.hash(id);}

二、OJ练习

2.1. 只出现一次的数字

        我们的基本思路是：利用HashSet，先遍历一遍数组，把集合中没有的数字放入，如果有，再移除，最后集合中剩下的元素就是只出现一次的数字，再遍历一遍数组，匹配HashSet中的数组。

        完整代码实现：

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

        执行时间还是比较高，因为使用了两次for循环遍历数组。

2.2. 随机链表的复制

        题目比较长，大概题意就是复制出一份与原来相同的链表。这道题的难点在于比单链表多了一个可以指向任意节点或者空的random域。起初，很多人会去想定义一个Node cur去遍历一遍链表，一个一个节点进行拷贝，但一拷贝就会发现问题，因为我们我们不知道cur.next和cur.random是哪一个节点的地址。既然遍历一遍链表不行，那就遍历两遍。第一遍遍历，所有节点的val域全都拷贝过来，next域以及random域全都默认为null，每遍历一个链表，就新实例化一个节点。然后我们<K,V>结构来建立老节点与新节点之间的映射关系。

        我们每获取一个节点的地址，都可以修改它的next域与random域。

        完整代码实现：

class Solution {public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();//第一遍遍历链表Node cur = head;while(cur != null){Node node = new Node(cur.val);map.put(cur,node);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);}
}

 2.3. 宝石与石头

        题目很简单，就是查找stones中含有jewels中的字符的个数。我们先遍历jewels字符串，将里面的字符放入集合中，再去遍历stones中的字符，最后返回宝石个数。

        完整代码实现：

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