常见的查找算法（下）哈希查找

发表于

哈希查找也称为散列查找，它是通过计算数据元素的存储地址进行查找的一种方法。

原文：http://www.cnblogs.com/maybe2030/p/4715035.html，这里在原文基础上加以补充修改。

哈希表与哈希函数

哈希表（Hash）

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素”分类”，然后将这个元素存储在相应”类”所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了”冲突”，换句话说，就是把不同的元素分在了相同的”类”之中。后面我们将看到一种解决”冲突”的简便做法。

总的来说，”直接定址”与”解决冲突”是哈希表的两大特点。

哈希函数

哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

六种哈希函数的构造方法：

  • 直接定址法：

    函数公式：f(key)=a*key+b (a,b为常数)

    这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。

  • 数字分析法：

    比如我们的11位手机号码“136XXXX7887”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意通，136是移动神州行，153是电信等。中间四们是HLR识别号，表示用户归属地。最后四们才是真正的用户号。

    若我们现在要存储某家公司员工登记表，如果用手机号码作为关键字，那么极有可能前7位都是相同的，所以我们选择后面的四们作为哈希地址就是不错的选择。

  • 平方取中法：

    故名思义，比如关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为哈希地址。

  • 折叠法：

    折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

    比如我们的关键字是9876543210，哈希表表长三位，我们将它分为四组，987|654|321|0 ，然后将它们叠加求和987+654+321+0=1962，再求后3位即得到哈希地址为962，哈哈，是不是很有意思。

  • ​ 除留余数法:

    函数公式：f(key)=key mod p (p<=m)m为哈希表表长。

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

  • 随机数法：

    函数公式：f(key)= random(key)。

    这里random是随机函数，当关键字的长度不等是，采用这种方法比较合适。

具体算法

算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程：

  • 用给定的哈希函数构造哈希表；

  • 根据选择的冲突处理方法解决地址冲突；

    常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。

  • 在哈希表的基础上执行哈希查找。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

复杂度分析：

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 7 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768 
typedef int Status;    
typedef struct
{
    int *elem; /* 数据元素存储地址，动态分配数组 */
    int count; /*  当前数据元素个数 */
}HashTable;
int m=0; /* 散列表表长，全局变量 */
/*初始化*/
Status Init(HashTable *hashTable)
{
    int i;
    m=HASHSIZE;
    hashTable->elem= (int *)malloc(m*sizeof(int)); //申请内存
    hashTable->count=m;
    for (i=0;i<m;i++)
    {
        hashTable->elem[i]=NULLKEY;
    }
    return OK;
}
/*哈希函数(除留余数法)*/
int Hash(int data)
{
    return data%m;
}
/*插入*/
void Insert(HashTable *hashTable,int data)
{
    int hashAddress=Hash(data);					   //求哈希地址
    while(hashTable->elem[hashAddress]!=NULLKEY)  //发生冲突
    {        
        hashAddress=(++hashAddress)%m;           //利用开放定址的线性探测法解决冲突
    }
    hashTable->elem[hashAddress]=data;           //插入值
}
/*查找*/
int Search(HashTable *hashTable,int data)
{
    int hashAddress=Hash(data);				 //求哈希地址
    while(hashTable->elem[hashAddress]!=data)   //发生冲突
    {
        hashAddress=(++hashAddress)%m;      //利用开放定址的线性探测法解决冲突
        if (hashTable->elem[hashAddress]==NULLKEY||hashAddress==Hash(data))
        	return -1;
    }
   
    return hashAddress;    //查找成功
}
/*打印结果*/
void Display(HashTable *hashTable)
{
    int i;
    printf("\n**********展示结果**********\n");
    for (i=0;i<hashTable->count;i++)
    {
        printf("%d ",hashTable->elem[i]);
    }
    printf("\n**********展示完毕**********\n");
}
void main()
{
    int i,j,result;
    HashTable hashTable;
    int arr[HASHSIZE]={13,29,27,28,26,30,38};
    printf("***************哈希查找(C语言版)***************\n");
    //初始化哈希表
    Init(&hashTable);
    //插入数据
    for (i=0;i<HASHSIZE;i++)
    {
        Insert(&hashTable,arr[i]);
    }
    Display(&hashTable);
    //查找数据
    result= Search(&hashTable,29);
    if (result==-1) printf("对不起，没有找到！");
    else printf("29在哈希表中的位置是:%d",result);
    getchar();
}

使用Hash的代价

我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair，经常使用Python的博友可能更有这种体会。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。

Hash算法和其他查找算法的性能对比：

search method efficient conclusion

工业上的应用

Hash算法在信息安全方面的应用主要体现在以下的3个方面：

  • 文件校验
    我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
    MD5 Hash算法的”数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
  • 数字签名
    Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称”数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
  • 鉴权协议
    如下的鉴权协议又被称作挑战–认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

参考：