- 哈希表是一种可以满足快速查找数据结构，时间复杂度接近O(1)。
- 哈希函数是无限集到有限集的映射。
- 处理数据量大，查找效率要求高时推荐使用hash容器。
- hash不一定优于数组查找，尤其在n比较小的情况下，可能hash算法的代价更高
- 问题：
- 什么情况下考虑使用哈希容器？
- 常用的哈希思路有哪些？
- 评判哈希算法标准有哪些？
- 哈希冲突是如何产生的？如何解决？
-
如何构造一个hash算法？应注意哪些问题？
-
效率高。
- 映射分布均匀。
直接寻址法：
取关键字key,使用线性函数 Hash(key) = a * key + b。
数字分析法：
在一个班级里，同龄学生很多。在取学生年龄作为key时，应避免以年份作为key组成部分。
平方取中法：
key取平方，截取中间的几位作为新的key。数学计算的性质乘积中间几位和乘数每一位都有关，充分混合key每一位对生成的哈希值的影响，使映射分布更均匀。
取余法：
Hash(key) = key % m
相乘取整法:
Hash(key) = floor(frac(key * A), m), 0
Original: https://www.cnblogs.com/hggzhang/p/16441310.html
Author: 张宏港
Title: Hash 哈希表和算法思路详解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588309/
转载文章受原作者版权保护。转载请注明原作者出处！