python散列函数设计 python 散列

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的对象。

代码如下：

Python数据结构-哈希表（Hash Table）

哈希表（Hash Table） ：通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

哈希函数（Hash Function） ：将哈希表中元素的关键键值映射为元素存储位置的函数。

哈希冲突（Hash Collision） ：不同的关键字通过同一个哈希函数可能得到同一哈希地址。

哈希表的两个核心问题是： 「哈希函数的构建」 和 「哈希冲突的解决方法」 。

常用的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。

常用的哈希冲突的解决方法有两种：开放地址法和链地址法。

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) = t ，同时又满足 abs(i - j) = k 。

如果存在则返回 true，不存在返回 false。

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

力扣217

力扣389

力扣496

内容参考：

第十九节-散列表（中）

散列函数的设计的好坏，决定了散列冲突的概率大小，也直接决定了散列表的性能。

过于复杂的散列函数，会消耗过多的计算时间，也就间接影响到散列表的性能。

这样才能避免或者最小化散列冲突。即便是出现冲突，散列到每个槽的数据也会分布得比较均匀，不会出现某个槽内的数据特别多的情况。

这些因素有关键字的长度、特点、分布、还有散列表的大小等。

通过分析传入散列函数的 key 的特征规律，设计相应的专用散列函数。比如处理使用散列函数处理手机号码，考虑到手机号码前几位重复性很大，后几位比较随机，我们就可以取手机号码后几位作为散列值。

比如对字符串进行散列，可以将字符串中每个字母的 ASCII 值进行“进位”相加，然后再跟散列表的大小求余、取模，作为散列值。比如，对因为单词 nice 进行散列：

hash("nice")=(("n" - "a") * 26*26*26 + ("i" - "a")*26*26 + ("c" - "a")*26+ ("e"-"a")) / 78978

装载因子的定义为 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度 ，根据这个公式，可以推出，装载因子越大且散列表的长度不变，则散列表中的元素越多，空闲位置越少，散列冲突的概率会变大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

对没有频繁插入和删除的静态数据集合来说，我们很容易根据数据的特点、分布等，设计出完美的、极少冲突的散列函数。

对于动态散列表来说，数据集合频繁变动，负载因子可能随着时间不断变大。这时就要动态扩容。

动态扩容的过程，简单来说，就是申请一个新的散列表，然后把原来的数据搬运到新的散列表中，但是不是简单的搬运，而是每个元素都要根据新的散列表重新存储位置。

这个过程，运用平摊分析法，每个插入操作的时间复杂度仍是 O(1)。

扩展一下，当散列表的装载因子小于某个阈值时，我们也可以依样画葫芦，进行动态缩容。

大部分情况下，动态扩容的散列表插入一个数据都很快，但在特殊情况下，装载因子达到扩容的阈值，此时，再插入数据，就会触发漫长的扩容过程，在特定的场合，这样漫长的等待过程是不可接受的。

举个直观的例子，假设原来散列表有 1GB 的数据，现在进行扩容，就需要对这 1GB 的数据进行再散列，这个扩容的时间，看起来就很耗时。

在这种情况下，“一次性”扩容的机制就不适合了。此时，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子达到扩容的阈值后，我们只申请新空间，但不立即将老的数据全部搬移到新的散列表中。

当有新的数据插入时，我们就将新数据插入新散列表中，同时从旧散列表中拿出一个数据放入到新的散列表。每次插入一个数据到散列表，我们都重复以上的过程。经过多次操作后，老的散列表中的数据就一点一点全部搬移到新的散列表中了。没有了一次性全部搬移，插入操作就不会出现一次很慢的情况了。

这期间的插入操作，可以先从新的散列表中查，查不到再去旧的散列表中查。甚至，可以在每次查询操作中也穿插一条数据搬移。

上节讲了两种主要的散列冲突的解决办法，开放寻址法和链表法。这两种冲突的解决办法在实际的软件开发中很常用。比如， Java 中的 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。

这种实现方式，散列表中的数据都存放在数组中，可以有效利用 CPU 的缓存加快查询速度。序列化过程比较简单。链表法包含指针，序列化就比较麻烦。

缺点是，删除数据比较麻烦，需要使用特殊标记。所有数据都存在一个数组中，冲突的代价很大。

总结，数据量小、装载因子小，适合开放寻址法。这也是 ThreadLocalMap 采用开放寻址法解决散列冲突的原因。

链表法的优点是内存利用率高。链表节点可以在需要的时候再创建，并不需要想开放寻址法那样实现申请好。

链表法对冲突的容忍性更高，装在因子可以大于 1，甚至再散列冲突很平均的情况下，即使装载因子达到 10，查找效率也不会大幅度衰退。更进一步，对链表法进行改造，使用红黑树或者跳表解决散列冲突，那即使是极端情况下，所有数据都存放在一个槽内，查询时间也是衰退到 O(logn) 的数量级。

缺点是，需要维持链表的指针引用，若是存放小对象，那么指针占用的内存就会对比起来挺多，而且链表法也容易造成内存碎片。

总结起来就是，基于链表法的散列冲突方法适合存储大对象、大数据量的散列表，而且比起开放寻址法，它更加灵活，支持更多的优化策略。

分析 HashMap

HashMap 的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量多少，就可以依此设置合适的初始容量。

最大装载因子默认是 0.75。当 HashMap 中元素个数超过 0.75 * capacity 时，就会启动扩容，每次扩容后的容量是原来的两倍。

关于 0.75 这个数字的由来，可以查看这篇文章 。

HashMap 底层采用链表法解决冲突。在 JDK 1.8 之前，冲突的元素插入链表首端，在 JDK 1.8 之后，插入尾端。

另外，在 JDK 1.8 之后，当链表长度超过 8 时，会启动树化，当树中元素少于 6 个时，会退化回链表。

HashMap 的二次哈希，使用的是除留余数法。

因为 A % B = A (B - 1)，所以，(h ^ (h 16)) (capitity -1) = (h ^ (h 16)) % capitity。

设计这样的散列表应该从三个方面考虑

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

Python如何哈希字符串

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

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

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

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

关于python散列函数设计和python 散列的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。