哈希表

使用哈希表可以进行非常快速的查找操作。但是，哈希表究竟是什么玩意儿？很多人避而不谈，虽然知道经常用到，很多语言的内置数据结构像python中的字典，java中的HashMap，都是基于哈希表实现。但哈希表究竟是啥？

哈希是什么？

(如果觉得废话很多，可以直接看建立哈希表)

散列（hashing）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。也译为散列。旧译哈希（误以为是人名而采用了音译）。它也常用作一种资讯安全的实作方法，由一串资料中经过散列算法（Hashing algorithms）计算出来的资料指纹（data fingerprint），经常用来识别档案与资料是否有被窜改，以保证档案与资料确实是由原创者所提供。 —-Wikipedia

哈希函数

所有的哈希函数都具有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。

哈希表

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

建立哈希表

这看了一堆概念，老衲甚为头疼。总的来说，哈希表就是一个具备映射关系的表，你可以通过映射关系由键找到值。有没有现成的例子？当然有，不过你直接用就没意思了。

反正就是要实现f(k)，即实现key-value的映射关系。我们试着自己实现以下：

class Map:
    def __init__(self):
        self.items=[]
    
    def put(self,k,v):
        self.items.append((k,v))
    
    def get(self,k):
        for key,value in self.items:
            if(k==key):
                return value

这样实现的Map，查找的时间复杂度为O(n)。
“这看上去与key没什么关系啊，这不是顺序查找么，逗我呢？”
这只是一个热身，好吧，下面我们根据定义，来搞一个有映射函数的：

class Map:
    def __init__(self):
        self.items=[None]*100
    
    def hash(self,a):
        return a*1+0
    
    def put(self,k,v):
        self.items[hash(k)]=v
    def get(self,k):
        hashcode=hash(k)
        return self.items[hashcode]

“这hash函数有点简单啊”
是的，它是简单，但简单不代表它不是哈希函数，事实上，它是由一种叫直接定址法的方法建立的哈希函数，是一个线性函数：
hash(k)= a*k+b

“为啥初始化就指定了100容量？”
要指出的是，这个是必须的。你想通过下标存储并访问，对于数组来说，这不可避免。在JDK源码里，你也可以看到，Java的HashMap的初始容量设成了16。你可能说，你这hash函数，我只要key设为100以上，这程序就废了。是啊，它并不完美。这涉及到扩容的事情，稍后再讲。

直接定址法的优点很明显，就是它不会产生重复的hash值。但由于它与键值本身有关系，所以当键值分布很散的时候，会浪费大量的存储空间。所以一般是不会用到直接定址法的。

处理冲突

假如某个hash函数产生了一堆哈希值，而这些哈希值产生了冲突怎么办（实际生产环境中经常发生）？在各种哈希表的实现里，处理冲突是必需的一步。
比如你定义了一个hash函数：
hash(k)=k mod 10
假设key序列为：[15,1,24,32,55,64,42,93,82,76]

1	2	3	4	5	6
1	32	93	24	15	76
	42		64	55
	82

一趟下来，冲突的元素有四个，下面有几个办法。

开放定址法

开放定址法就是产生冲突之后去寻找下一个空闲的空间。函数定义为：

其中，hash(key)是哈希函数，di是增量序列，i为已冲突的次数。

线性探测法

hash_table

即di=i，或者其它线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，然后放置在该单元。

[15,1,24,32,55,64,42,93,82,76]

可以看到，在55之前都还没冲突：

0	1	2	3	4	5	6	7	8	9
	1	32		24	15

此时插入55，与15冲突，应用线性探测，此时i=1，可以得到：

0	1	2	3	4	5	6	7	8	9
	1	32		24	15	55

再插入64，冲突不少，要取到i=3：

0	1	2	3	4	5	6	7	8	9
	1	32		24	15	55	64

插入42，i=1：

0	1	2	3	4	5	6	7	8	9
	1	32	42	24	15	55	64

插入93，i=5：

0	1	2	3	4	5	6	7	8	9
	1	32	42	24	15	55	64	93

插入82，i=7：

0	1	2	3	4	5	6	7	8	9
	1	32	42	24	15	55	64	93	82

插入76，i=4：

0	1	2	3	4	5	6	7	8	9
76	1	32	42	24	15	55	64	93	82

发现越到后面，冲突的越来越离谱，因为表的大小选择也很重要，此例中选择了10作为表的大小，所以容易产生冲突。一般来讲，越是质数，mod取余就越可能分布的均匀。

平方探测

hash_table

这称作平方探测法，一个道理，也是查找到一个空单元然后放进去。这里就不一步一步说明了=。=
伪随机探测
di是一个随机数序列。
“随机数？那get的时候咋办？也是随机数啊，怎么确保一致？”
所以说了，是伪随机数。其实我们在计算机里接触的几乎都是伪随机数，只要是由确定算法生成的，都是伪随机。只要种子确定，生成的序列都是一样的。序列都一样，那不就可以了么=。=

链表法

这是另外一种类型解决冲突的办法，散列到同一位置的元素，不是继续往下探测，而是在这个位置是一个链表，这些元素则都放到这一个链表上。java的HashMap就采用的是这个。

再散列

如果一次不够，就再来一次，直到冲突不再发生。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(注意：在这个方法里面是把元素分开两个表来存储)。

说了这么一堆，举个例子，用开放地址法（线性探测）：

class Map:
    def __init__(self):
        self.hash_table=[[None,None]for i in range(11)]
    
    def hash(self,k,i):
        h_value=(k+i)%11
        if self.hash_table[h_value][0]==k:
            return h_value
        if self.hash_table[h_value][0]!=None:
            i+=1
            h_value=self.hash(k,i)
        return h_value
 
    def put(self,k,v):
        hash_v=self.hash(k,0)
        self.hash_table[hash_v][0]=k
        self.hash_table[hash_v][1]=v
    def get(self,k):
        hash_v=self.hash(k,0)
        return self.hash_table[hash_v][1]

“能不能不要定死长度？11个完全不够用啊”

这是刚才的问题，所以有了另外一个概念，叫做载荷因子（load factor）。载荷因子的定义为：
α= 已有的元素个数/表的长度

由于表长是定值， α与“填入表中的元素个数”成正比，所以， α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子 α的函数，只是不同处理冲突的方法有不同的函数。

所以当到达一定程度，表的长度是要变的，即resize=。=像java的HashMap，载荷因子被设计为0.75；超过0.8，cpu的cache missing会急剧上升。可以看下这篇讨论：
https://www.zhihu.com/question/22911718

具体扩容多少，一般选择扩到已插入元素数量的两倍，java也是这么做的。

接着上面，再升级一下我们的map：

class Map:
    def __init__(self):
        self.capacity=11
        self.hash_table=[[None,None]for i in range(self.capacity)]
        self.num=0
        self.load_factor=0.75
    
    def hash(self,k,i):
        h_value=(k+i)%self.capacity
        if self.hash_table[h_value][0]==k:
            return h_value
        if self.hash_table[h_value][0]!=None:
            i+=1
            h_value=self.hash(k,i)
        return h_value
    def resize(self):
        self.capacity=self.num*2 #扩容到原有元素数量的两倍
        temp=self.hash_table[:]
        self.hash_table=[[None,None]for i in range(self.capacity)] 
        for i in temp:
            if(i[0]!=None):  #把原来已有的元素存入
                hash_v=self.hash(i[0],0)
                self.hash_table[hash_v][0]=i[0]
                self.hash_table[hash_v][1]=i[1]
 
    def put(self,k,v):
        hash_v=self.hash(k,0)
        self.hash_table[hash_v][0]=k
        self.hash_table[hash_v][1]=v
        self.num+=1                 #暂不考虑key重复的情况，具体自己可以优化
        if(self.num/len(self.hash_table)>self.load_factor):# 如果比例大于载荷因子
            self.resize()
    def get(self,k):
        hash_v=self.hash(k,0)
        return self.hash_table[hash_v][1]

看上面的函数，可以看到resize是一个比较耗时的操作，更何况作为一个python小白的我写的不是很好。可以去看一下Java的HashMap的hash方法和resize方法，其中的思路要精妙的多。

关于哈希表，原理的东西都基本差不多了。可以看到，它本质要解决的是查找时间的问题。如果顺序查找的话，时间复杂度为O(n)；而哈希表，时间复杂度则为O(1)！直接甩了一个次元有木有，这也就是为什么在大量数据存储查找的时候，哈希表得到大量应用的原因。

哈希表

哈希表