散列表
数据经过散列函数后映射的数据存储位置而形成的表。
其目的在于加快数据查找速度，经过映射后直接在散列表中访问数据。
散列函数
- 期望，key1 != key2 —> hash(key2) != hash(key1)
- 原始输入不同，经过散列函数映射的值也不同。
- 同时，散列值不可逆，推测出真正的输入值。
- 散列碰撞、哈希碰撞，散列值相同的情况下，可能出现相同输入值。
常见的散列函数
- MD5 Message-Digest Algorithm 5（信息-摘要算法5）常用于下载文件完整性检查。
- SHA-1 Secure Hash Algorithm 1：安全散列算法1 被称为MD5继承者
散列冲突、哈希冲突不可消除原因
抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。
正如上面数学中"抽屉原理"，散列表作为数据存储的"抽屉"，当遇到所需要查询映射的"苹果"数量远远大于"抽屉"数量的时候，必然出现一个散列表地址出现两个相同的散列值出现。
散列、哈希冲突的解决之道
- 开放寻址法 不断找到哈希表中空闲位置，实现有：线性探测法、二次探测法、双重散列法
- 链表法 常用的哈希冲突解决办法，就是直接在哈希表每个位置多一个链表，遇到散列值相同就直接放到链表里面。
