python实现散列函数的简单介绍

Python如何哈希字符串

Python中字符串是可哈希的，即可以作为字典的键或者HashTable的键使用。

成都创新互联公司技术团队十多年来致力于为客户提供成都网站建设、做网站、成都品牌网站建设、营销型网站建设、搜索引擎SEO优化等服务。经过多年发展，公司拥有经验丰富的技术团队，先后服务、推广了成百上千网站，包括各类中小企业、企事单位、高校等机构单位。

您可以这样子使用Python内置函数hash（散列函数）：

您也可以将字符串转为一个集合：

总之，Python里面有很多内置的hash功能性数据结构和函数。

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的特点。

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也是采用了哈希表实现，但是在发生哈希冲突的时候采用的是链接法。