代码随想录04:哈希表

BBigSun 评论188阅读模式

代码随想录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')

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 31日 08:11:48
  • 转载请务必保留本文链接:https://www.bbigsun.com/410.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定