散列表

基本概念

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

原理

散列表被用于大海捞针式的查找。

我们知道，简单查找算法的时间复杂度为O(n),二分查找的时间复杂度为O(logn),而散列表的时间复杂度为O(1)!!

来做一个比较，比如我们将所有商品的价格写在一个本子上，有顾客来买东西时，我们需要查找到对应商品的价格。

散列函数

基本概念

散列函数，又称为散列算法，哈希函数。可以将一个任意的数据压缩为一个固定长度的字符串，这个字符串叫做散 列值，或者是消息摘要。所以，也可以叫做摘要算法。散列值通常用一个短的随机字母和数字组成的字符串来代 表。好的散列函数在输入域中很少出现散列冲突。

散列函数的性质

如果两个散列值不同，那么这两个散列值在进入散列函数之前的原始数据也必定不同。

origionA -> value1

origionB -> value2

value1 不等于 value2

所以origionA 也不可能等于origionB

具有这种性质的散列函数叫做单向散列函数。

但是，如果两个原始数据，不同，它们的输出值是可能相等的。

origionC -> value3

origionD -> value3

origionC 不等于 origionD,但是，它们两个通过散列函数计算后的值都是value3

这中情况被叫做"散列碰撞(collision)",这通常是两个不同长度的输入值，刻意计算出相同的输出值。

一个好的散列函数，是不能具有可逆性的，即我们不能通过输出值，来计算出原始数据。

常见的散列函数

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。

MD5（RFC 1321）是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以 512 位分组，其输出是 128 位。MD5 比 MD4 复杂，并且计算速度要慢一点，更安全一些。MD5 已被证明不具备"强抗碰撞性"。

SHA （Secure Hash Algorithm）是一个 Hash 函数族，由 NIST（National Institute of Standards and Technology）于 1993 年发布第一个算法。目前知名的 SHA-1 在 1995 年面世，它的输出为长度 160 位的 hash 值，因此抗穷举性更好。SHA-1 设计时基于和 MD4 相同原理，并且模仿了该算法。SHA-1 已被证明不具"强抗碰撞 性"。

为了提高安全性，NIST 还设计出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（统称为 SHA-2），跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

散列函数的应用

1. 保护数据

   比如我们平时从网站上下载文件，文件的提供者同时会给出文件的md5值或sha256值，我们下载完成后，可以通过计算出文件的md5或sha256来和正确的值进行对比，实现防篡改的功能。

   还有就是我们平常在网站注册新用户时，数据库存放的并不是我们输入的密码的明文格式。我了解的大多数的方法是md5(password + salt),salt叫做加盐，是一个随机的值。如果不这样的话，那我们的个人数据还不满天飞。当然，就是有很多厂商，甚至是很多特别大的公司，竟然使用明文的格式存放用户的信息，真不知道怎么想的。

2. 散列表

   散列表是散列函数的一个主要应用，能够让服务程序从大量的数据中快速的找到我们想要的信息。

3. 错误矫正

   使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。--维基百科

   个人感觉和第一个应用保护数据的思想差不多。。。

4. 语音识别

   对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。

   那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够健壮的散列函数确实存在。现存的绝大多数散列算法都是不够健壮的，但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的健壮性。有一个实际的例子是Shazam[1] 服务。用户可以用手机打开其app，并将话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名 --维基百科

   我们平常使用的音乐软件上的听歌识曲就是这个应用。

散列表在Python中的实现

散列表在Python中是通过字典的形式组织的。

我们知道python字典的key是唯一的，这也就确保了查找的唯一性。

Text['method'] = 'md5'
Text['function'] = 'sha256'
​
print(Text['method'])

这里我只是对哈希表做了一个简单的介绍，接下来我会总结具体的哈希算法的实现,比如md5,sha256..