哈希表(Hash Table)
哈希 Table HASH
2023-09-27 14:27:39 时间
参考:
Hash table - Wiki
我们身边的哈希,最常见的就是perl和python里面的字典了,字典有什么性质,给定键就可以直接找到值,字典封装了一种映射关系(散列函数),它和数组完全不同,数组是根据地址来访问值。
定义:给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
这个世界上没有十全十美的东西,所以我们要学会取舍。任何技术的实现都没有最好的只要最合适的,也就说实现的最佳方案是和应用场景息息相关的。
很多时候,我们想对数据进行快速的存取(比如缓存的实现),并用一个key来标记自己存取的数据。我们可以把它叫做key-value的结构。
说到“快速”我们很快想到数组,因为数组可以在O(1)的时间复杂内完成指定位置元素的读写操作。
所以在理想状态,如果一个数组足够长,且存在一个函数可以将每一个key映射到唯一的一个数组下标,那么我们就可以很完美的解决问题。但往往资源都是有限的,我们没有那么大的空间,也不能设计一个无比负责的映射算法保证每一个key对应到一个唯一的数组下标。所以我们会选择一些折中的方案。hash table便是为解决这类问题而存在的。
相关文章
- 【BZOJ5211】[ZJOI2018]线图(树哈希,动态规划)
- 哈希函数3:布隆过滤器,用位图标记黑名单系统,用哈希函数设置位图
- 1145 Hashing - Average Search Time (25 分)【难度: 一般 / 知识点: 哈希表平均查找时间】
- 1137 Final Grading (25 分)【难度: 一般 / 知识点: 排序 哈希表】
- 1020 Tree Traversals (25 分) 【难度: 中 / 知识点: 哈希表建树 遍历树】
- 并发数据结构-1.6 哈希表
- 局部敏感哈希算法介绍
- 一致性哈希算法
- 哈希表-拉链-数据读取-考虑冲突
- HMAC是一种利用哈希函数构造消息认证码的方法
- 一致性哈希算法的领悟
- 72、【哈希表】leetcode——454. 四数相加 II(C++版本)
- 哈希表和完美哈希
- 五分钟理解一致性哈希算法(consistent hashing)
- 高性能分布式哈希表FastDHT