哈希函数
是将给定数据转化为固定长度的不规则值的函数。
将数据输入到哈希函数中，会输出不规则的值。
输出的不规则的值称之为hash值。
哈希值是一个数字，通常用16进制表示
{D85E620C-3F95-08B4-0F62-B40A2C1FB036}.jpg
哈希函数的特征
- 输出值的长度不变。
输出数据的长度取决与哈希函数，例如在SHA-1的情况下，它固定为20字节。不论输入的数据或大或小，输出的哈希值的数据长度页不会改变。 -
相同的输入值，那么它们的输出值也是相同的。
{4CAFFC8B-4C49-8EB9-601C-7686E6D0AABE}.png
-
即使输入的两个数据之间相差非常少，但是输出值却相差很大。
{82A615F6-67D4-63FA-47E3-CA908F45DED4}.png
- 输入完全不同的数据，也会有极低的概率输出相同的哈希值。（哈希碰撞）（拉链法，再哈希法等等）
{7790B432-7ADF-E415-8DAB-7BD23E238787}.png
-
哈希值的运算是不可逆的，不能通过哈希值来获取原数据。
{49155CB4-FC6C-529B-370D-D020676A506F}.png
常用的哈希算法
MD4，MD5，SHA-0，SHA-1，SHA-2。
{4983CB0C-EFA7-FF51-9D95-51A8891F2503}.png
哈希表
哈希表是一种数据结构。
擅长以“keys”和“values“组成的集合存储数据。
{63B2B590-E71B-FB3F-E254-BE198DEF2F83}.jpg
在这种情况下，名字是”keys“，而性别是”value“。
可以将图标中的数据想象为一个数组。
{097E6C06-3086-D879-7204-CBC98FE2514A}.jpg
查找Ally的性别，因为我们不知道Ally存储在第几个盒子中，因此我们需要从头开始搜索，这个操作被称为”线性搜索“。
线性搜索操作的成本和数据大小成正比,在搜索大量数据是会耗费大量资源。
哈希表解决了这个问题，我们会先准备一个数组来存储一些数据，存储Joe的数据时，我们使用哈希函数计算密钥的哈希值，这种情况我们得到结果4928。
{4FE3D470-1081-5961-6859-F7357BE44550}.png
将查找到的哈希值除以数组中的盒子数5，求出余数，（这个操作成为mod操作）
mode操纵的结果为3，我们就把Joe的数据存储在数组的第三个盒子中。
重复该操作。
当我们进行mode计算的结果处已经被占用时，会将数据以列表的形式链接到现有元素，（链式方法）。
{8427D62F-D7D9-3DC9-EEB2-E456E42BAE1C}.jpg
在进行数据检索时，我们会对key进行哈希运算后进行mode运算，得到数据存储的大致位置，如果该位置是一个列表，就在列表上进行线性搜索。找到key对应的value。
使用哈希表可以快速的访问到数组中的数据。
注意：
如果用于哈希表的数组太小，则重复会增加，进行线性搜索的可能性也会增加。
如果数组太大，会有很多数据盒子没有存储数据，浪费内存。!
网友评论