HASH TABLES 哈希表

2017-09-29 BoobooWei

Hash Table 简介

哈希表（Hash table，也叫散列表）:是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。
hash函数（散列法）就是找到一种数据内容和数据存放地址之间的映射关系。

Hash Table 的应用

你在哪里遇到过hash这个词语呢？

应用场景总结

Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
查找：哈希表，又称为散列，是一种更加快捷的查找技术。

Hash表在海量数据处理中有着广泛应用。

Hash Table 的原理

建立一个哈希表之前需要解决两个主要问题：

构造一个合适的哈希函数：

均匀性 H（key）的值均匀分布在哈希表中；
简单以提高地址计算的速度

冲突的处理：

冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）= H（K2）。
均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。

Hash函数

重点掌握以下Hash函数：

平方取中法

除留余数法（取模）

哈希表中元素是由哈希函数确定的。将数据元素的关键字Key作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为：

Addr = H（key）

直接定址法

直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址

适于：地址集合的大小 = = 关键字集合的大小，其中a和b为常数。

公式：

H（k）=k  或 H（k）=a×k+b  
其中 a , b 为常数

举例：

有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图
可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。

如果我们要统计的是80后出生的人口数，如上表所示，那么我们对出生年份这个关键字可以用年份减去1980来作为地址，此时f(key)=key-1980
这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。

数字分析法

假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

适于：能预先估计出全体关键字的每一位上各种数字出现的频度。

举例：

要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示：

K1=61317602      K2=61326875      K3=62739628      K4=61343634
K5=62706815      K6=62774638      K7=61381262      K8=61394220

分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：2，75，28，34，15，38，62，20。

平方取中法

这是一种常用的哈希函数构造方法。

先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。

适于：关键字中的每一位都有某些数字重复出现频度很高的现象

公式：

H(key)=key^2的中间几位

原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。

举例：

若设哈希表长为1000则可取关键字平方值的中间三位，如图所示：

关键字	关键字的平方	哈希函数值
1234	1522756	227
2143	4592449	924
4132	17073424	734
3214	10329796	297

折叠法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：

移位叠加：将分割后的几部分低位对齐相加；
边界叠加：从一端沿分割界来回折叠，然后对齐相加。

所谓折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。

适于：关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。

举例：

当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则这两种叠加情况如图：

    移位叠加                              边界叠加
    8 9 1                                     8 9 1
    1 1 9                                     9 1 1
    3 3 1                                     3 3 1
    1 0 8                                     8 0 1
 +  1 1 0                                   + 1 1 0              
(1) 5 5 9                                  (3)0 4 4

由折叠法求哈希地址

用移位叠加得到的哈希地址是559，而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串，则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。

除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

适于：

公式：

H(key)=key MOD p (p<=m)

举例：

已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有

h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
h(46)=46 % 7=4

此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：

h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   
h(46)=46 % 13=7

此时没有冲突，如下所示。

0	1	2	3	4	5	6	7	8	9	10	11	12
		54		43	18		46	60		75		90

除留余数法求哈希地址理论研究表明，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址。

适于：对长度不等的关键字构造哈希函数。

公式：

H(key)=random(key）,其中random为随机函数

其他算法

旋转法
字符串数值哈希法
随机乘数法

冲突的处理

链接法（拉链法）
开放定址法
桶定址法
多哈希法
探测再散列
建域法

拉链法

拉链法是最常用的一种方，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

Hash Table 的插入和查找步骤

查找步骤

当存储记录时，通过散列函数计算出记录的散列地址
当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

插入步骤

若已知哈希函数及冲突处理方法，哈希表的建立步骤如下：

取出一个数据元素的关键字key，计算其在哈希表中的存储地址D=H(key）。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；否则发生冲突，执行Step2。
根据规定的冲突处理方法，计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。

优缺点

优点：

不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。
哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：

它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

实例（海量数据处理）

我们知道hash 表在海量数据处理中有着广泛的应用，下面，请看另一道百度面试题题目：

海量日志数据，提取出某日访问百度次数最多的那个IP。

方案

首先过滤出 "指定的天" and "访问百度" 的日志中的IP取出来，逐个写入到一个大文件中。

如下阐述（作者雪域之鹰）：
算法思想：分而治之+Hash
1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理； 
2.可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址； 
3.对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；
4.可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；

Python代码实现

使用了 readlines 将文件分块读入内存，然后hash并序列化保存(这里为了方便用了JSON序列化缓存到文本，IO开销很大，在真实的使用环境中可以缓存到数据库)，在python3.x中使用了readlines后 tell 不能再用了，两个函数冲突。

在py2.7中open函数没有encoding参数，要注明 encoding 必须使用codecs模块的codecs.open。

#coding:utf-8  
#py3.x  
import re  
import json  
import time  
import os  
  
def run(logpath, hashcode,topnum=100):  
    for i in range(0, hashcode):  
        with open(str(i), 'w', encoding='utf-8') as f:  
            f.write('{}')  
    h = 50*1024 * 1024#50MB  
    with open(logpath, 'r', encoding='utf-8-sig') as f:  
        lines=f.readlines(h)  
        while lines:  
            lineshandler(lines, hashcode)  
            lines=f.readlines(h)  
    return orderresult(hashcode,topnum)  
  
def lineshandler(lines,hashcode):  
    ipreg=re.compile('\d+\.\d+\.\d+\.\d+')  
    d={}  
    for i in range(0,hashcode):  
        with open(str(i),'r',encoding='utf-8') as f:  
            d[i]=json.loads(f.read())  
    for line in lines:  
        if line.startswith('#'):  
            continue  
        else:  
            ips=re.findall(ipreg,line)  
            if len(ips)<2:  
                continue  
            else:  
                ip=ips[1]  
            hid=hash(ip)%hashcode  
            d[hid].setdefault(ip,0)  
            d[hid][ip]+=1  
    for hid in d.keys():  
        with open(str(hid),'w',encoding='utf-8') as f:  
            f.write(json.dumps(d[hid]))  
  
  
def orderresult(hashcode,topnum):  
    l=[]  
    for i in range(0, hashcode):  
        with open(str(i), 'r', encoding='utf-8') as f:  
            d=json.loads(f.read())  
            for key in d.keys():  
                if len(l)<topnum:  
                    l.append((key,d[key]))  
                    if len(l)==topnum:  
                        l=sorted(l,key=lambda x:x[1],reverse=True)  
                else:  
                    if l[topnum-1][1]<d[key]:  
                        l.pop(topnum-1)  
                        l.append((key,d[key]))  
                        l=sorted(l,key=lambda x:x[1],reverse=True)  
        os.remove(str(i))  
    return l  
  
t1=time.time()  
rs = run('u_ex130702.log',9,10)  
t2=time.time()  
print(rs)  
print('共用时'+str(t2-t1)+"秒")