python散列函数算法 常用的散列函数

python dict 实现原理 2019-04-17

dict对象是Python中一个原始的数据类型，按照键值对的方式存储，中文名为字典，其通过键名查找对应的值有很高的效率，时间复杂度在常数级别O(1)。Python dict的底层是依靠哈希表(Hash Table)进行实现的，使用开放地址法解决冲突。所以其查找的时间复杂度会是O(1)，why？

哈希表是key-value类型的数据结构，通过关键码值直接进行访问。通过散列函数进行键和数组的下标映射从而决定该键值应该放在哪个位置，哈希表可以理解为一个键值需要按一定规则存放的数组，而哈希函数就是这个规则。

算法中时间和空间是不能兼得的，哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作，这取决于具体的功能要求。

创建一个数组，数组下标是索引号，数组中的值是要获得的数据，这样只需要O(1)的时间复杂度就可以完成操作，但是扩展性不强，有以下两个方面的考虑：

-1- 新添加的元素超出数组索引范围，这就需要重新申请数组进行迁移操作。

-2- 假设一种极端的情况：只存在两个元素，索引号分别是1和100000000001，按照先前的设计思路，会浪费很大的存储空间。

会不会存在一个方法，为已有的索引创建新的索引，通过压缩位数，让新索引可以和原有的大范围的稀疏索引进行一一对应，新索引所需要的存储空间要大大减小，这就是哈希思想。

上面的例子中哈希函数的设计很随意，但是从这个例子中我们也可以得到信息：

哈希函数就是一个映射，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可；

因为新的索引对旧的索引进行了空间上的压缩，所以不可能所有的输入都只对应唯一一个输出，也就是哈希函数式有可能发生冲突的，哈希函数不可能做成一对一的映射关系，其本质是一个多对一的映射。

直接定址法：很容易理解，key=Value+C； 这个“C”是常量。Value+C其实就是一个简单的哈希函数。

除法取余法： 很容易理解， key=value%C;解释同上。

数字分析法：这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。

平方取中法。此处忽略，见名识意。

折叠法：这种蛮有意思,比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相关，来做到“散列地址”尽可能分散的目地。

当两个不同的数据元素的哈希值相同时，就会发生冲突。解决冲突常用的手法有2种：

开放地址法：

如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。

链接法：

将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。

python的dict采用了哈希表，最低能在 O(1)时间内完成搜索，在发生哈希冲突的时候采用的是开放寻址法。java的HashMap也是采用了哈希表实现，但是在发生哈希冲突的时候采用的是链接法。

相关问答

Q1: python之哈希算法

哈希(Hash)算法：`hash（object）`

哈希算法将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。是一种信息摘要算法。对象的hash值比原对象拥有更低的内存复杂度。

它不同于加密。哈希（hash）是将目标文本转换成具有相同长度的，不可逆的杂凑字符串，而加密则是将文本转换为具有相同长度的，可逆的密文。

哈希（hash）算法是不可逆的，只能由输入产生输出，不能由输出产生输入。而加密则是可逆的。即可以从输入产生输出，也可以反过来从输出推出输入。

对于hash算法，不同的数据应该生成不同的哈希值。如果两个不同的数据经过Hash函数计算得到的Hash值一样。就称为哈希碰撞（collision）。哈希碰撞无法被完全避免。只能降低发生概率。

好的hash函数会导致最少的hash碰撞。

*

可哈希性（hashable）：

可哈希的数据类型为不可变的数据结构（如字符串srt，元组tuple，对象集objects等）。这种数据被称为可哈希性。

不可哈希性：

不可哈希的数据类型，为可变的数据结构（如字典dict，列表list和集合set等）。

如果对可变的对象进行哈希处理，则每次对象更新时，都需要更新哈希表。这样我们则需要将对象移至不同的数据集，这种操作会使花费过大。

因此设定不能对可变的对象进行hash处理。

**

**

Python3.x添加了hash算法的随机性，以提高安全性，因此对于每个新的python调用，同样的数据源生成的结果都将不同。

哈希方法有（MD5, SHA1, SHA256与SHA512等）。常用的有SH256与SHA512。MD5与SHA1不再常用。

- MDH5 (不常用)

- SHA1 (不常用)

- SHA256 (常用)

- SHA512 (常用)

一种局部敏感的hash算法，它产生的签名在一定程度上可以表征原内容的相似度。

可以被用来比较文本的相似度。

安装simhash：

Pip3 install simhash

感知哈希算法（perceptual Hash Algorithm）。用于检测图像和视频的差异。

安装Imagehash:

pip3 install Imagehash

比较下面两张图片的Imagehash值

可以看到两张图片的hash值非常相似。相似的图片可以生成相似的哈希值是Imagehash的特点。

Q2: Python数据结构与算法-哈希map的实现及原理

1-collections.MutableMapping

1.1 概念：这是什么？

大家可能想知道这一串英文是什么意思？其实只需要了解在collections库当中有一个非常重要的抽象基类MutableMappin

g，专门用于实现map的一个非常有价值的工具。后边我们会用到它。

2-我们的map基类

2.1 实现这个类

这个基类其实也就是确定了键值对的属性，并且存储了基本的比较方法。它的对象就是一个键值对咯。这个很好理解。有点类似object的感觉。

3-通过map基类实现的无序映射

给大家看一个上边的例子，这个例子来源于网络，自己改了改，能用，更加详细而已，凑合看.

4-Python哈希表的实现的基类

4.1 咱有话直说：上才（代）艺（码）

如果还不知道哈希表概念的同xio，请参考 python进阶之数据结构与算法–中级-哈希表（小白piao分享） 。废话不多说，咱们撸代码：

OK了，基本的哈希表就实现了，其实仔细想想很容易，但是自己要能实现还是要理解哈希表的本质哦，外加一定量的练习才可以熟练掌握，练习的目的就是为了熟练而已。

5-分离链表实现的具体哈希map类

说明：这玩意只是一种降低冲突的手段，上一节提过，降低冲突最好的地方是发生在元组进入桶的时候，所以想必大家猜到了，接下来的分离链表也就是为了self._bucket_xxxxxxx系列方法做准备。这里之所以在上边使用@abstractmethod就是为了继承实现，目的可以实现多种将冲突的哈希表。分离链表的概念上一节也有的。

“见码入面”（借鉴：见字如面这个电视节目，有兴趣可以看看，还不错的）：

6-用线性探测处理冲突的哈希map类

这种方式的好处不需要再去借助其他额外的赋值结构来表示桶。结构更加简单。不会再像上一种方法还要让桶是一个UnsortedTableMap的对象。

代码如下：

Q3: python md5不可逆又怎么使用数据

MD5不可逆的原因是其是一种散列函数，使用的是hash算法，在计算过程中原文的部分信息是丢失了的。

MD5即Message-Digest Algorithm 5（信息-摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一（又译摘要算法、哈希算法），主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。