哈希表理论基础

文章：1. 哈希表理论基础

哈希表是根据关键码的值而直接进行访问的数据结构

直白来讲，数组就是一张哈希表

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。

一般解决的问题：一般哈希表都是用来快速判断一个元素是否出现在集合里。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后可以通过查询索引下标，就可以快速知道这位同学是否在这所学校里了。

哈希函数，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转换为不同的数值，这样就可以把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会再次对数值做一个取模的操作，就让我们保证了学生姓名一定可以映射到哈希表上。

如果学生数量大于哈希表的大小怎么办？此时就算哈希函数计算的再均匀，也避免不了会有几个学生的名字 同时映射到哈希表同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

学生姓名都映射到了同一个索引下标的位置，这一现象叫做哈希碰撞

一般有两种解决方法，拉链法和线性探测法。

拉链法

hashCode：1 -> 小李 -> 小王

拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费时间。

线性探测法

使用线性探测法一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

冲突了就存到下一位

常见的三种哈希结构

  • 数组
  • set（集合）
  • map（映射）
集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 否 否 O(log n) O(log n)
std::multiset 红黑树 有序 是 否 O(logn) O(logn)
std::unordered_set 哈希表 无序 否 否 O(1) O(1)

std::unordered_set底层实现为哈希表，std::和std::multiset的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但是key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们需要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

map，在map是一个 key value 的数据结构，map中，对key是有限制，对value是没有限制的，因为key的存储方式是使用红黑树实现的。

其他语言例如：java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

【总结】

当我们需要快速判断一个元素是否出现在集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242.有效的字母异位词

文章：3. 两个数组的交集

题目：242. 有效的字母异位词

视频：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词_哔哩哔哩_bilibili

【思路】

字母异位词：aabc = bcaa

判断是不是由相同字母组成即可。

哈希表的三种形式：数组、set、map

题目提出数据只有小写字母组成，意味着只有a到z 26个字母。ascii码是连续的。

因此a可以对应到数组下标为 0 的数字，b 对应1，所以我们可以定义一个大小为26的数组即可。

通过遍历第一个字符串得到每个字母出现的次数++，再遍历第二个字符串每个字母出现的次数–。最后再遍历数组，如果数组的值均为0 说明是字母异位词；如果出现值不为 0 的情况则说明不是字母异位词，立即返回false。

数据量较小的可以考虑使用数组进行存储。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isAnagram(String s, String t) {
        if(t.length() != s.length())return false;
        int[]arr = new int[26];
        for(int i = 0;i < s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        for(int i = 0 ; i < t.length();i++){
            arr[t.charAt(i) -'a']--;
        }
        for(int i : arr){
            if(i != 0)return false;
        }
        return true;
    }
}
  • Go实现

我们可以使用range对数组进行遍历；rune('a')用于将字符'a'转换为对应的unicode码点，该unicode码点被用作record切片的索引，对相应位置的元素进行自增操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isAnagram(s string, t string) bool {
    record := [26]int{}
    for _,s := range s{
        record[s-rune('a')]++  //unicode解法
    }
    for _,s := range t{
        record[s-rune('a')]--
    }
    /*for _,i := range record{
        if i != 0{
            return false
        }
    }
    return true*/
    return record == [26]int{}  //简易写法
}

349.两个数组的交集

文章：3. 两个数组的交集

题目：349. 两个数组的交集

视频：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集_哔哩哔哩_bilibili

【思路】

哈希的三种形式：数组、set、map

哈希表最擅长去解决：一个元素是否在集合里面出现过

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

题目要求去重。本题我们用set来解决。

首先我们将数组1的全部元素放进哈希表里面，然后遍历数组 2 查询哈希表里面是否有数组 2 的值，如果有重复就可以将值存进set里面（顺便可以去重）。最后将set转换成数组类型返回即可。

  • Java实现

对于set转换为数组不熟悉：

//方法一：
return set2.stream().mapToInt(x -> x).toArray();
//方法二：另外申请一个数组存放set2的元素
int[] arr = new int[set2.size()];
int j = 0;
for( int i : set2 ){
arr [ j++ ] = i;
}
return arr;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer>set1 = new HashSet<>();
        HashSet<Integer>set2 = new HashSet<>();
        for(int i : nums1){
            if(!set1.contains(i)){
                set1.add(i);
            }
        }
        for(int i : nums2){
            if(set1.contains(i)){
                set2.add(i);
            }
        }
        //方法一：
        //return set2.stream().mapToInt(x -> x).toArray();
        //方法二：另外申请一个数组存放set2的元素
        int[]arr = new int[set2.size()];
        int j = 0;
        for(int i :set2){
            arr[j++] = i;
        }
        return arr;
    }
}
  • Go实现

增强循环不是很熟练；使用map模拟set不是很熟练；对if _,ok := set[i];ok使用不熟；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func intersection(nums1 []int, nums2 []int) []int {
    set := make(map[int]struct{},0)
    res := make([]int, 0 )
    for _,i := range nums1{
        if _,ok:=set[i];!ok{
            set[i]=struct{}{}//struct集合
        }
    }
    for _,i := range nums2{
        //如果存在于上一个数组，则加入res，同时清空在set的键
        if _,ok := set[i];ok{
            res = append(res,i)
            delete(set,i)
        }
    }
    return res
}

202.快乐数

文章：4. 快乐数

题目：202. 快乐数

判断算出来的数值是否==1 或 重复。如果 ==1 则返回 true，!=1 则返回 false。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isHappy(int n) {
        if (n ==1)return true;
        HashSet<Integer> set = new HashSet<>();
        while( calNums(n) != 1 ){
            if(set.contains(calNums(n)))return false;
            set.add(calNums(n));
            n = calNums(n);
        }
            return true;
    }
    public int calNums(int n){
        int sum =0;
        while(n != 0){
            int temp = n%10;
            n = n/10;
            sum += temp*temp;
        }
        return sum;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isHappy(n int) bool {
    set := make(map[int]bool)
    for n != 1 && !set[n]{//如果出现重复的值则退出循环
        n,set[n]=calNum(n),true
    }
    return n == 1 
}

func calNum(n int)int {
    sum := 0
    for n != 0{
        temp := n%10
        n /= 10
        sum += temp*temp
    }
    return sum
}

1.两数之和

文章：5. 两数之和

题目：1. 两数之和

视频：梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！_哔哩哔哩_bilibili

这题使用哈希三种类型的map。

我们可以寻找map中是否存在target-nums[i]的值，如果有返回即可；如果没有，则将当前遍历到的数组值及其下标一同添加进map中。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[]res = new int[2];
        //如果选择将数组的数全部先存进map的话会出现重复的数字相加刚好等于target的情况
        /*for(int i = 0 ; i < nums.length;i++){
                map.put(nums[i],i);
        }*/
        for(int i = 0 ; i < nums.length;i++){
            int temo = target-nums[i];
            if(map.containsKey(temo)){
                res[0] = map.get(temo);
                res[1] = i;
                break;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}
  • Go实现

Go语法方面，暂时还不太能灵活的将map看作数组进行处理，但是这个思维值得学习。

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i:=0;i<len(nums);i++{
        if val,ok:=m[target - nums[i]];ok{
            return []int{val,i}
        }
        m[nums[i]] = i
    }
    return []int{}
}

【算法总结】

  • 学习了哈希表的基础理论；哈希表的三种方式：数组、set（有序）、map（无序）；map和set均可去重；
  • 有效的字母异位词学习了在一个数组内通过将小写字母和数组下标联系起来，有效的节省了空间和时间；
  • 两个数组的交集学习了如何找重复的元素；
  • 快乐数学习了查找map中是否出现重复运算的值作为突破点。

【语法总结】

  • Java：对于set转换为数组不熟悉：

    //方法一：
    return set2.stream().mapToInt(x -> x).toArray();
    //方法二：另外申请一个数组存放set2的元素
    int[] arr = new int[set2.size()];
    int j = 0;
    for( int i : set2 ){
    arr [ j++ ] = i;
    }
    return arr;

  • Go：

    • 我们可以使用range对数组进行遍历；rune('a')用于将字符'a'转换为对应的unicode码点，该unicode码点被用作record切片的索引，对相应位置的元素进行自增操作。

    • 增强循环不是很熟练；使用map模拟set不是很熟练；对if _,ok := set[i];ok使用不熟；

    • 暂时还不太能灵活的将map看作数组进行处理