代码随想录04：哈希表

什么是哈希表？

英文名 Hash Table，中文名 散列表。文章源自十年又十年-https://www.bbigsun.com/410.html

官方解释：哈希表是根据关键码的值而直接进行访问的数据结构。文章源自十年又十年-https://www.bbigsun.com/410.html

举例：数组是哈希表，关键码是 0、1、2...，值是 array[0]、array[1]、array[2]...文章源自十年又十年-https://www.bbigsun.com/410.html

解释：查询数组中某个学生的名字，如果是通过枚举的方法，时间复杂度为 O(n)，如果是通过索引，时间复杂度为 O(1)。文章源自十年又十年-https://www.bbigsun.com/410.html

举一反三：数据库中经常查询的数据，可以添加索引，提高查询速度。文章源自十年又十年-https://www.bbigsun.com/410.html

哈希表如何实现的？

学生的姓名通过哈希函数转化为hashCode映射到哈希表的索引上，如果hashCode大于哈希表的tableSize，则对 hashCode 取模操作，保证 hashCode 一定在 tableSize内。文章源自十年又十年-https://www.bbigsun.com/410.html

如果两个学生映射到了同一个索引，这种现象叫哈希碰撞。此时，有两种解决方法：拉链法和线性探测法。拉链法是在同一个索引位置添加链表（合适的哈希表大小，否则浪费空间时间）。线性探测法是在该索引下方找一个空位进行存储（tableSize > dataSize）文章源自十年又十年-https://www.bbigsun.com/410.html

常见的三种哈希结构

• 数组
• set（集合）
• map（映射）

有效的字母异位词

问题描述：给定两个字母 s 和 t，判断 t 是否为 s 的字母异位词文章源自十年又十年-https://www.bbigsun.com/410.html

示例1：输入：s='anagram',t='nagaram', 输出：true文章源自十年又十年-https://www.bbigsun.com/410.html

示例2：输入：s='rat',t='cat',输出：false文章源自十年又十年-https://www.bbigsun.com/410.html

字符串只包含小写字母

思路：定义一个 26 位数组 record，因为 a-z 小写字母正好 26个，定义一个哈希函数，将a-z映射为0-25，分别遍历字母 s 和 t，记录下二者的 record，如果相同则为 true，不同则为 false。

hashfuc = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,...}
def get_record(s):
    record = [0] * 26
    for i in s:
        record[hashfunc[i]] += 1
    return record

if get_record(s) == get_record(t):
    print('true')
else:
    print('false')