算法系列之哈希表_四元组哈希

前端仔一只，不时刷刷算法题防止老年痴呆。本文是个人算法系列中的一篇，如果想了解更多关于算法的内容，请点击博主的算法专栏查看。

注意：本文所有的代码都采用 JavaScript。所有题目来自 leetcode。全部答案通过了测试，可放心食用。

理论回顾

哈希思想

哈希表（Hash Table）用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有哈希表。

哈希表有两个关键点需要了解，一个是哈希函数，另一个是哈希冲突。这也是构造哈希表的两个关键要素。

哈希函数

哈希函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过哈希函数计算得到的哈希值。

哈希冲突

再好的哈希函数也无法避免哈希冲突，我们常用的哈希冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

理论知识就简单回顾到这。如果读者从来没有了解过哈希表，那建议找一篇理论文章读一读，本文这里仅仅带大家回顾一些关键概念点。

真题演练

有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例：

输入: s = "anagram", t = "nagaram"
输出: true
1
2

输入: s = "rat", t = "car"
输出: false
1
2

解答

本题难度为简单，有多种解法。这里主要介绍利用哈希表求解的方法。

思路： 对 s 和 t 个进行一次遍历，第一次统计每个字母出现的个数。第二次如果出现存在哈希表的字母，那么其个数减一。最后统计哈希表中每个 key 的个数，如果都为 0，那么两者为异位词，否则，不是。

var isAnagram = function(s, t) {
   
    if (s.length !== t.length) {
   
        return false
    }
    const hashmap = new Map()
    for (let i = 0; i < s.length; i++) {
   
        if (!hashmap.has(s[i])) {
   
            hashmap.set(s[i], 0)
        }
        hashmap.set(s[i], hashmap.get(s[i]) + 1)
    }
    for (let i = 0; i < t.length; i++) {
   
        if (!hashmap.has(t[i])) {
   
            return false
        }
        hashmap.set(t[i], hashmap.get(t[i]) - 1)
    }
    for (let key of hashmap.keys()) {
   
        if (hashmap.get(key) !== 0) {
   
            return false
        }
    }
    return true
};
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
26
27
28
29
30
31
32