目录
Hash表是一种的数据结构。它是加速算法里最常见的工具。这种数据结构可以提速。
如果说 O (log N )已经很不错了，但你学习 哈希表 这种结构后，你会发现它可以在 O(1)时间内查找数据、O(1)时间内插入数据。这个速度，基本上很难超越了 ，Log N在他面前只能是个弟弟。
学习哈希表的工作原理和适用场景后，你可以在许多地方发挥它的速度优势。如果你要构建高效的软件，Hash是不可避免的。
Hash表的别名
- Hash
- Map
- Hash Map
- Dictionary
- Associate Array
The working principle
插入操作
先做一个字母和数字的映射表：
A=1
B=2
C=3
D=4
E=5
......
基于这个字母和数字的映射表，设计一个简单的Hash函数，我们使用求积的方式：
现实的hash函数要复杂很多，上面我们只是教学用。
注意：hash函数必须要满足对同样字符串使用hash函数得到的值必须永远相同：
插入的过程：
查找操作
Hash表的查找原理
hash表只能单向查找
解决键冲突问题
有一个问题，上面的Hash函数，DAB也会转换为8。这里有一个巨大的问题，
另外插入一个问题，hash表，把键存在哪里？
不同语言有不同的设计。....
现在回答一下，bad和dab两个hash值重复，该怎么解决？
- 了解拉链法
遍历的时候：
Hash的应用场景
-
数据本身就是成对的，非常适合用Hash
- 菜单中的菜品和价格
- 积分表
- 候选人和得票数
- ...
-
简化逻辑
-
对象的属性
-
快速查找场景
-
去重场景
Hash的键有重复项不能存入，达到去重的效果；