Loading... # Python实现Dict > **Hash表**也称为**散列表**，是一种线性数据结构。在一般情况下，可以用`O(1)`的时间复杂度进行数据的增删改查。 ## 什么是Hash表 **Hash表**是一种线性数据结构，这种数据结构的底层一般是由数组实现的。在进行数据增删改查的时候，Hash表首先通过Hash函数对某个键值进行Hash操作，这个Hash操作会将这个键映射到数组的某个下标，获得下标以后就可以直接对数组中的数据进行操作了。理论上讲，Hash表数据操作的时间复杂度都是`O(1)`。  Hash表的底层是通过数组实现的。**数据有个特点就是：必须在初始化的时候指定其长度。**所以当Hash表中的数据填满之后想继续向里面放数据的话就必须再创建一个容量更大的数组，然后将之前数组中的数组copy到这个新数组中。这个过程是一个耗费性能的操作，因此我们在使用Hash表之前最好估算下数据的容量，尽量避免扩容操作。 ## Python中的Dict > CPython的字典实现为**可调整大小的哈希表**。与B-树相比，这在大多数情况下为查找（目前最常见的操作）提供了更好的性能，并且实现更简单。 > > 字典的工作方式是使用 [`hash()`](https://docs.python.org/zh-cn/3/library/functions.html#hash) 内置函数计算字典中存储的每个键的hash代码。hash代码根据键和每个进程的种子而变化很大；例如，"Python" 的hash值为-539294296，而"python"(一个按位不同的字符串)的hash值为1142331976。然后，hash代码用于计算内部数组中将存储该值的位置。假设您存储的键都具有不同的hash值，这意味着字典需要恒定的时间 -- O(1)，用Big-O表示法 -- 来检索一个键。 > > 来自官方文档：https://docs.python.org/zh-cn/3/faq/design.html#how-are-dictionaries-implemented-in-cpython ## 什么是Hash函数 哈希函数又称为散列函数，**就是把任意长度的输入**，通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 哈希函数的性质： - 哈希函数拥有无限的输入值域； - 当哈希函数输入一致时，输出必相同； - 当哈希函数传入不同的输入值时，返回值可能一样，也可能不一样； - 对于不同的输入所得的输出值会均匀分布； - 另外，Hash函数还具有如下两个性质： - **免碰撞**：即不会出现输入 x≠y ，但是H(x)=H(y) 的情况，其实这个特点在理论上并不成立，比如目前比特币使用的 SHA256 算法，会有2^256种输出，如果我们进行2^256 + 1 次输入，那么必然会产生一次碰撞，事实上，通过 理论证明 ，通过2^130次输入就会有99%的可能性发生一次碰撞，不过即使如此，即便是人类制造的所有计算机自宇宙诞生开始一直运算到今天，发生一次碰撞的几率也是极其微小的。 - **隐匿性**：也就是说，对于一个给定的输出结果 H(x) ，想要逆推出输入 x ，在计算上是不可能的。如果想要得到 H(x) 的可能的原输入，不存在比穷举更好的方法。 常用的Hash函数有：SHA1、MD5、SHA2等 实际应用举例： 我们平时使用的网盘，文件上传前就会计算出`hash code`，如果`hash code`已存在，即可达到所谓的“秒传”，因为这个文件经其他用户上传过的，直接转存至我们的网盘即可，无需再慢慢等上传。 ## Python简易实现Dict > Dict是一个可调整大小的hash表，hash表这个数据结构底层一般是由数组实现。 ```python class MyDict(object): def __init__(self, size: int = 10): self.size = size self.keys = [None for _ in range(self.size)] self.values = [None for _ in range(self.size)] # self.result = [None for _ in range(self.size)] def __hashfunc(self, key) -> int: return hash(key) % 3 def __haskey(self, key) -> bool: """ 判断key是否存在 """ h = self.__hashfunc(key) if self.keys[h] is None: return False return True def __setattr(self, key, value): h = self.__hashfunc(key) if self.keys[h] is None: self.keys[h] = key self.values[h] = value else: # 更新值 if self.keys[h] == key: self.values[h] = value # self.result[h][1] = value # 冲突 线性探测法 else: for i in range(h+1, self.size): if self.keys[i] is None: self.keys[i] = key self.values[i] = value break def __getattr(self, key): h = self.__hashfunc(key) print(self.keys) print(h) if self.keys[h] is None: # key不存在 raise KeyError(key) # 判断key是否相同 elif self.keys[h] == key: return self.values[h] else: # 不同则冲突，线性探测法 for i in range(h+1, self.size): if self.keys[i] == key: return self.values[i] raise KeyError(key) def setattr(self, key, value): self.__setattr(key, value) def getattr(self, key): return self.__getattr(key) def __setitem__(self, key, value): self.__setattr(key, value) def __getitem__(self, key): return self.__getattr(key) if __name__ == "__main__": mydict = MyDict() # mydict.setattr('a', 'b') # mydict.setattr('d', 'e') # mydict.setattr('f', 'g') # print(mydict.getattr('a')) # print(mydict.getattr('d')) # print(mydict.getattr('f')) mydict['a'] = 'b' mydict['d'] = 'e' mydict['f'] = 'g' print(mydict['a']) print(mydict['d']) print(mydict['f']) ``` ## Hash碰撞 **当哈希函数传入不同的输入值时，返回值可能一样，也可能不一样**，这种情况称为**hash碰撞或hash冲突** 常用解决方案： - 链地址法（拉链法） - 开放地址法 ### 链地址法 核心思想是：如果Hash表的某个位置上发生了Hash冲突（也就是说在将一个元素放置到数组中某个位置的时候，这个位置上已经有其他元素占据了），那么将这些元素以链表的形式存放。 上图  链表的查询效率是比较低的，所以如果在Hash表的某个位置上发生冲突的次数太多的话，那么这个位置就是一个很长的链表。查询速度较慢。 在Java 8中，HashMap做了一个优化，就是当链表长度达到8时，会自动将链表转换成**红黑树**，查询效率较高（**红黑树是一种自平衡的二叉查找树**）。 ### 开放地址法 在开放地址法中，若数据不能直接存放在哈希函数计算出来的数组下标时，就需要寻找其他位置来存放。在开放地址法中有三种方式来寻找其他的位置，分别是**线性探测、二次探测、再哈希法**。 #### 线性探测法 插入：首先对元素进行hash映射，如果映射的位置上为None，则插入；有数据，则判断下一个位置是否为空，如果没有则插入有则继续向后寻找，直到找到空位。 查询：通过键值定位到数组下标位置，将此位置上数据的值与待查找数据的值对比，如果相等则找到，否则继续向后查找，遍历结束都还未找到，则不存在 删除：首先还是通过键值映射到数组某个下标的位置，然后通过数组中元素的值和你要删除的元素的值进行比较，找出你要删除的那个元素。这里的删除可以理解为逻辑删除，将此位置设置为空即可。如果是实际删除，那么这个数组的后续元素下标均会发生改变，增加了维护数组的成本。 #### 二次探测法 在线性探测哈希表中，数据会发生聚集，一旦聚集形成，它就会变的越来越大，那些哈希函数后落在聚集范围内的数据项，都需要一步一步往后移动，并且插入到聚集的后面，因此聚集变的越大，聚集增长的越快。这个就像我们在逛超市一样，当某个地方人很多时，人只会越来越多，大家都只是想知道这里在干什么。 二次探测是防止聚集产生的一种尝试，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。在线性探测中，如果哈希函数得到的原始下标是x,线性探测就是x+1,x+2,x+3......，以此类推，而在二次探测中，探测过程是x+1,x+4,x+9,x+16,x+25......,以此类推，到原始距离的步数平方。 #### 再哈希法 双哈希是为了消除原始聚集和二次聚集问题，不管是线性探测还是二次探测，每次的探测步长都是固定的。双哈希是除了第一个哈希函数外再增加一个哈希函数用来根据关键字生成探测步长，这样即使第一个哈希函数映射到了数组的同一下标，但是探测步长不一样，这样就能够解决聚集的问题。 第二个哈希函数必须具备如下特点： - 和第一个哈希函数不一样； - 不能输出为0，因为步长为0，每次探测都是指向同一个位置，将进入死循环，经过试验得出 `stepSize=constant-(key%constant)`;这种形式的哈希函数效果非常好，constant是一个质数并且小于数组容量。 双hash的核心思想是，第二步生成一个随机的探测步长。 ## 参考文章 https://www.cnblogs.com/54chensongxia/p/11566973.html Last modification：November 10th, 2020 at 08:24 pm © 允许规范转载