哈希表是一个非常强大的数据结构，我本篇系列的文章，我们会讲述以下内容
- 什么是哈希表(Hash table),什么是散列函数(hash function)?
- 散列函数的属性
- 解决散列算法的冲突问题，其中流行的方案是开放寻址和单独链接，因此我们将要衍生讨论线性探测和二次探测的完成方式，本篇后续会以示例讲解他们的工作原理
- Separate chaining 实现的细节
什么是哈希表
哈希表就是一种使用散列算法(Hashing)提供从键到值的映射的数据结构，下面就是键值对的映射示例，我们只要通过一个唯一可识别的名称即可映射到对应该名字的年龄，像这样的映射关系，我们叫做键值对(key-value pairs)
ss8.png
因此在哈希表中,键可以是任意的数据类型，只要它是键中是唯一的即可映射到一个值,而值是不必唯一的。
哈系表的用途
哈系表经常用于分类统计和跟踪键中的对象出现的频率
理解哈希表中的键值对(key-value pairs)构成，首选需要了解什么散列函数
散列函数
简单地说，散列函数h(x)是将键x映射到固定范围内的整数的函数，我们看看看一些简单的哈希函数的示例
ss8.png
这是一个不好的示例，因为键部分插入该示例函数会得到产生多个相同的值，例如h(4)和h(9)，h(8)和h(12)都分别映射到同一个数字，这是没问题的，我们不仅可以在证书上定义任意的散列函数，还可以在任意对象上定义任意哈希函数，这使得这一函数非常强大
例如对于字符窜，我们可以定义一个和ascii码相关的散列函数h(x)的伪代码
function H(str):
sum:=0
for c in s:
sum+=ascii(c)
return sum mod 50
这个散列函数所做的就是对字符串中的字符ASCII值求和，然后在结尾处做取模运算，所以对于任何给定的字符串，它只输出一个数字，这就是一个散列函数,如下图不同的字符串传入H(x)会得到随机散列值
ss8.png
有了前面的基础，我们讨论一个更添加实际开发中的例子，例如我们有一个person的关系表，通常person表中每条记录有三个字段Name,Age,Sex构成一个person对象的基本特征信息,散列函数是的算法可以是任意可能的算法组合,但最终要的是散列函数在计算传入对象的散列值的的时间开销能能维持O(1)是最为理想的
ss8.png
我们希望为每个person对象的特征定义散列函数H(p)，能够映射到集合{0,1,2,3,4,5,6}，这次为了简化示例，我们使用python代码定义了下面关于Person对象的散列函数hash(p),该散列函数的起始计算元素是Person.age,接着Person.name，接着是Person.sex，最后是以除数7做取模运算
class Person:
def __init__(self,name,age,sex):
self.name=name
self.age=age
self.sex=sex
#end-def
#end-class
def hash(p):
hs=p.age
hs=hs+len(p.name)
if p.sex=='M':
hs+=1
return hs % 7
#end-def
p1=Person('Golden',24,'M')
p2=Person('Cally' ,32,'F')
p3=Person('Mady' ,27,'F')
p4=Person('Cat' ,49,'M')
p5=Person('Zucy' ,15,'M')
pList=[p1,p2,p3,p4,p5]
for p in pList:
print("Person对象:{} - hash:{}".format(p.name,hash(p)))
上面代码的每个Person对象的散列值的运算结果如下表
ss8.png
散列函数的属性
- 如果h(x)≠h(y),那么x≠y 也就是说，x和y是两个不同的对象
-
如果h(x)=h(y),那么x=y
也就是说，如果我们有一个散列函数，并且两个对象分别由x和y并且它们的散列值相等，那么这两个对象可能相等，我们不确定是否必须显式地检测x和y，三列函数告诉我们在x和y散列值相同的位置发生了冲突
由上面的散列函数的属性引申出一个问题，
如何利用这个优势来加快对象比较?答案就是我们在初始化对象x和y之初应计算出两个对象的散列值,比较x,y的散列值的时间消耗要优于显式遍历x,y对象并比较他们的属性
在下面这个例子中，考虑尝试确定两个大文件是否具有相同的内容的问题
如果我们预编译了file1和fil2，首先应该比较这些哈希值，因为比较哈希值是O(1)，如果可能，我们不想直接打开任何一个文件。逐个字节地比较它们的内容会很慢，尽管我们 如果H（file1）= H（file2），则可能必须这样做。
注意：用于文件的哈希函数比用于哈希表的哈希函数更复杂，对于文件，我们使用所谓的加密哈希函数，也称为校验和
- 散列函数的另外一个属性就是其散列值必须绝对确定的
这意味这如果y=h(x),那么h(x)必须总能产生y并且不可能是另外的值(字符串或整数)，这可能很明显，但是对于哈希函数的功能至关重要
那么什么是非确定性呢？这个很容易理解
读者可以看看上文的示例的散列函数，我们基本上在散列函数内部定义一个基本数据类型的局部变量，这是散列函数绝对确定性的关键。因为它们都没有用到全局变量作为计算散列值的数据源，也就是非确定性的函数引用了全局变量会造成每个传入对象的散列值的不确定性
冲突
散列冲突(Hash Collision)就是指当两个对象m,n传入某个散列函数h(x)返回了相同的散列值，即h(m)=h(n),在哈系表插入操作中我们简称冲突(collison)，上面的示例中，都不同程度地出现了冲突
在实现哈希表时,我们尽可能使散列函数减少散列冲突的次数,这样做的原因是为了使哈希函数值域中的所有值都能够命中，以便可以均匀地填充到表中
什么是可散列化
现在，我们可以回答有关允许在哈希表中使用的键类型的核心问题,什么使T类型的键(Key)可散列化？
答： 因为我们要在哈希表的实现中使用散列函数，所以我们需要散列函数是绝对确定性的。为了强制这种行为，我们要求哈希表中使用的键(Key)是不可变的数据类型。如果T类型的键是不可变的，并且我们为T类型的所有键k定义了哈希函数H(k)，那么我们称之为键类型T是可散列(hashable)
哈希表如何工作？
理想情况下，我们希望对放入哈希表中的数据有非常快的插入，查找和删除时间。散列函数为我们提供了在哈希表中查找对应元素的索引，值得注意的是，仅当您具有算法设计良好的哈希函数时，我们可以使用哈希函数在O(1)时间内将所有这些操作，以此作为索引到哈希表的方式，而哈希表只是数组的一个奇特的称呼罢了。
如下图是一个哈希表的逻辑图，每次向表中插入元素时，需通过散列函数计算被插入元素的散列值，对应的散列值就是表中的索引，查找元素也时，同理，只需计算键对应的散列值就能找到表中对应索引的元素。随着表中插入元素的增多，冲突的概率就大大增加，例如键Golden和键Mady的数据项是冲突的，
那么在哈希表中有许多方案解决散列冲突，流行的解决方案主要有
- 开放寻址(open addressing)：此法的思想是通过探测并在哈希表中查找与我们最初进行散列对应的位置在偏移后的另一个位置来处理哈希冲突。这里你如果不明白的话，我打个通俗的比喻，比如广东人去酒楼就早茶需要提前预订位置的，比如你定的桌子的编号和其他人冲突了,那么酒楼经理就会为你另外安排另外一个编号桌子一样。
- 单独链表(separate chainning)：此法的思想是通过维护数据结果来处理冲突，通常是一个链表，链表内包含所有为某个特定散列值的所有不同的键值对
哈希表的时间复杂度
只有在具有良好设计的均匀散列函数时，哈希表在平均情况下的下列操作的常量时间行为才能成立，
均匀散列函数:就是为任意的传入对象生成的散列值，任意两个传入对象发生冲突的可能性最低的散列函数，事实上是散列冲突是无法避免的，但如果你在一次固定次数的插入操作中产生冲突的次数超过你插入次数的10%的话（这是我个人所定的测试基准），你就要审视你写的散列函数就需要重构了
小结
我们本篇只要介绍了哈希表的一个最核心的主体，那就是散列函数(Hash Function)它是构成整个哈系表，且有别于普通数组的重要基石。下一篇我们会详细介绍避免散列冲突的技术--开放寻址(Open Addressing)的基本原理
网友评论