type
status
date
slug
summary
tags
category
icon
password
哈希函数
哈希函数其实就是单向搅拌器，比如输入 abc，输出 7f0579bc2d
特点
1、不管输入字符串长度长短，结果位数固定
2、相同的输入的输出也必定相同
3、即使输入了相似的数据，如果他们相差1比特，输出也会有很大不同（输入相似的数据，输出一般不相似，如果相似，只是巧合）
4、位数固定就确定了只有有限位数的结果，有可以忽略不计的重复概率，也叫生日碰撞或哈希值的冲突
5、单向，不可逆推。不可能通过结果计算输入的值
哈希表
哈希表就是 Keys 和 Values 组成的集合存储数据
每个 key 对应一个 value，我们可以将一对 key value 看成一个盒子，或者一个模型
线性搜索是不稳定的、数据较多时是耗时的，哈希表就是为了解决这个问题
例如我们有一个数组，数组空间只够存放 5 个盒子
我们要在 0 号位置放第一个盒子，盒子的 key 为 “张三”，value 为 28 （岁），会先将 key （张三）通过哈希函数换算成一个 Int 整形结果，例如 4567，再拿 4567 除以盒子总空间数 5，取出余数为 2，此时就会把 key（张三） 和 value（28） 打包进一个盒子里，放进 2 号位置
第二个要放的盒子 key 为 “李四”，value 为25，通过哈希函数得到结果 3100，取出余数为 0，放进 0 号位置
第二个要放的盒子 key 为 “王五”，value 为30，通过哈希函数得到结果 2007，取出余数为 2，放进 2 号位置，但是这时 2 号位置已经存在了一个数据为 “张三”，那么 “王五” 就会以链表的形式添加在 “张三” 的后边
像这种以链表形式存在的数据存储的盒子，在查找时如果发现盒子内大于一个数据，会进行遍历，直到找到相同的 key，这也是 key 要存储在盒子中的原因
第四、第五个数据存储方式同上
我们看到，当哈希值重叠时，将使用列表进行处理，如果用于哈希表的数组的大小太小（位置数量较少），则会增加使用数组进行线性搜索的可能性。所以在数据量较小时不适合使用 Hash 表
- 作者:NotionNext
- 链接:https://tangly1024.com/article/Hash%20%E5%87%BD%E6%95%B0%E5%92%8C%20Hash%20%E8%A1%A8
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章