python 下的数据结构与算法---8：哈希一下【dict与set的实现】

少年，不知道你好记不记得第三篇文章讲python内建数据结构的方法及其时间复杂度时里面关于dict与set的时间复杂度[为何访问元素为O(1)]原理我说后面讲吗？其实就是这篇文章讲啦。

　　一：Hash的定义

　　二：dict与set的实现原理

　　三：常用构造hash函数的方法

　　四：hash碰撞及其解决方法

　　五：dict的实现

一：Hash的定义

　　Hash，一般翻译做“散列”，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。【不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值】

二：dict与set的实现原理

　　dict与set实现原理是一样的，都是将实际的值放到list中。唯一不同的在于hash函数操作的对象，对于dict，hash函数操作的是其key，而对于set是直接操作的它的元素，假设操作内容为x，其作为因变量，放入hash函数，通过运算后取list的余数，转化为一个list的下标，此下标位置对于set而言用来放其本身，而对于dict则是创建了两个list，一个list该下表放此key，另一个list中该下标方对应的value。

　　其中，我们把实现set的方式叫做Hash Set，实现dict的方式叫做Hash Map/Table(注：map指的就是通过key来寻找value的过程)

三：常用构造hash函数的方法

　　1：折叠法

　　　　将每个元素分为相等的几部分后相加后再除以list长度，e.g：如果项目是436-555-4601, 以2为分组，分成了 (43, 65, 55, 46, 01). 全部加起来：43 + 65 + 55 + 46 + 01 = 210. 假设list有11个元素, 则210%11 =1, 所以将436-555-4601放到list下标为1的地方。

　　2：取中法：

　　　　如元素44平方后得1936取中93再取list的余

　　注：对于string其所对应的数字可用其ASCII码来代替（还可与位数结合，见图5.7）ord('a')可返回'a'的ASCII码

　　注：此地就是为什么dict与set访问元素时间复杂度为O(1)的原因了，通过对元素的hash函数运算后能够直接知道其下标，所以为O(1)

四：hash碰撞及其解决方法

　　定义里面讲到过不同的输入可能会散列成相同的输出，所以就可能出现名为“哈希碰撞”的情况，也就是说两个不同的元素算出来的下标值一样，此时就有两种解决方法:

　　1:向后探测

　　　　　　架设一个元素算出来下标为5，另一个元素算出来下标也为5，从开头开始探测第0第1位是否为空，当看到为空的就放入，不过这样相邻探测的不好之处在于容易发生聚集，所以最好是跳跃着进行探测，定义一个skip的值，比如3，用方程rehash(pos) = (pos + skip)%sizeoftable，即使查看0，3，6这样跳跃着来

　　2：链式存储

　　　　原理图如下，其实就是将发生有冲突的元素放到同一位置，然后通过“指针“来串联起来

五：HashTable

　　下面将写一个hashTable，而实际中的dict就是由hashTable扩展而来的

 1 class HashTable:
 2     def __init__(self):
 3         self.size = 11
 4         self.slots = [None] * self.size
 5         self.data = [None] * self.size
 6 
 7     def hash_function(self, key, size):
 8         return key % size
 9     def rehash(self, old_hash, size):
10         return (old_hash + 1) % size
11     def __getitem__(self, key):
12         return self.get(key)
13     def __setitem__(self, key, data):
14         self.put(key, data)
15 
16     def put(self, key, data):
17         hash_value = self.hash_function(key,len(self.slots))
18         if self.slots[hash_value] == None:
19             self.slots[hash_value] = key
20             self.data[hash_value] = data
21         elif self.slots[hash_value] == key:
22             self.data[hash_value] = data        # replace
23         else:
24             next_slot = self.rehash(hash_value, len(self.slots))
25             while self.slots[next_slot] != None and self.slots[next_slot] != key:
26                 next_slot = self.rehash(next_slot, len(self.slots))
27                 if self.slots[next_slot] == None:
28                     self.slots[next_slot] = key
29                     self.data[next_slot] = data
30                 else:
31                     self.data[next_slot] = data     #replace
32 
33     def get(self, key):
34         start_slot = self.hash_function(key, len(self.slots))
35         data = None
36         stop = False
37         found = False
38         position = start_slot
39         while self.slots[position] != None and not found and not stop:
40             if self.slots[position] == key:
41                 found = True
42                 data = self.data[position]
43             else:
44                 position=self.rehash(position, len(self.slots))
45                 if position == start_slot:
46                     stop = True
47         return data

HashTable