数据结构之查找（七）——散列表查找（哈希表）

散列技术

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应 一个存储位置f（key），即存储位置=f（关键字）。我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。关键字对应的记录存储位置我们称为散列地址。

散列表查找步骤

（1）在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。

（2）当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。

散列技术既是一种存储方法，也是一种查找方法。散列主要是面向查找的才存储结构。散列技术最适合的求解问题是查找与给定值相等的记录。

俩个关键字 key1！=key2，但是却有f（key1）=f（key2），这种现象我们称为冲突（collision），并把key1和key2称为这个散列函数的同义词（synonym）。

散列函数的构造方法

原则

1.计算简单；

2.散列地址分布均匀。

常用的散列函数构造方法

1.直接定址法

取关键字的某个线性函数值为散列地址，即f（key）=a*key+b（a，b为常数）

优点：简单，均匀，不会产生冲突。

缺点：需要事先知道关键字的分布情况，适合查找表较小且连续的情况。

2.数据分析法

若我们用手机号存储公司员工登记表，那么我们选择后面的四位成为散列地址就是不错的选择。如果还是容易出现冲突问题，可以对抽取出来的数字在进行反转，右环位移，左环位移，甚至前俩数与后俩数叠加等方法。

抽取方法是使用关键字的一部分来计算散列存储的方法，这在散列函数中是常常用到的手段。

数据分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

3.平方取中法

假设关键字1234，那么平方就是1522756，再抽取中间的3位就是226，用做散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用做散列地址。

平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

4.折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

如关键字是9876543210，散列表表长为三位，将其分为四组，987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为926.

折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

5.除留余数法

此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：f（key）=key mod  p （p<=m）。

mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠，平方取中后再取模。

本方法的关键就在于选择合适的p，p如果选得不好，就可能容易产生同义词。

因此根据前辈们的经验，若散列表表长为m，通常p 为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

6.随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。即f（key）=random（key）。这里random是随机函数。

当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

现实中，应该视不同的情况采用不同的散列函数。下面是一些参考因素：

1.计算散列地址所需的时间；

2.关键字的长度；

3.散列表的大小；

4.关键字的分布情况；

5.记录查找的频率。

处理散列冲突方法

开放定址法

开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列列表足够大，空的散列地址总能找到，并将记录存入。

当本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。

1.线性探测法

它的公式是：

2.二次探测法

它的公式是：

3.随机探测法

它的公式是：

这里的随机数其实是伪随机数。

再散列函数法

对于我们的散列表来说，我们事先准备多个散列函数。

这里的RHi就是不同的散列函数，可以把前面的什么除留余数，折叠，平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算。这个方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。

链地址法

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词表的头指针。

如：关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}，用前面同样的12为除数，进行除留余数法，可得如图结构：

链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。

公共溢出法

为所有冲突的关键字建立一个公共的溢出区来存放。

就前一个例子而言，将冲突的关键字存储到溢出表中，如图：

如果相对基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

散列表查找的实现

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
#include "stdafx.h"
#include<iostream>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768 

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
	int *elem; /* 数据元素存储基址，动态分配数组 */
	int count; /*  当前数据元素个数 */
}HashTable;

int m = 0; /* 散列表表长，全局变量 */

		   /* 初始化散列表 */
Status InitHashTable(HashTable *H)
{
	int i;
	m = HASHSIZE;
	H->count = m;
	H->elem = (int *)malloc(m * sizeof(int));
	for (i = 0; i<m; i++)
		H->elem[i] = NULLKEY;
	return OK;
}

/* 散列函数 */
int Hash(int key)
{
	return key % m; /* 除留余数法 */
}

/* 插入关键字进散列表 */
void InsertHash(HashTable *H, int key)
{
	int addr = Hash(key); /* 求散列地址 */
	while (H->elem[addr] != NULLKEY) /* 如果不为空，则冲突 */
	{
		addr = (addr + 1) % m; /* 开放定址法的线性探测 */
	}
	H->elem[addr] = key; /* 直到有空位后插入关键字 */
}

/* 散列表查找关键字 */
Status SearchHash(HashTable H, int key, int *addr)
{
	*addr = Hash(key);  /* 求散列地址 */
	while (H.elem[*addr] != key) /* 如果不为空，则冲突 */
	{
		*addr = (*addr + 1) % m; /* 开放定址法的线性探测 */
		if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循环回到原点 */
			return UNSUCCESS;	/* 则说明关键字不存在 */
	}
	return SUCCESS;
}

int main()
{
	int arr[HASHSIZE] = { 12,67,56,16,25,37,22,29,15,47,48,34 };
	int i, p, key, result;
	HashTable H;

	key = 39;

	InitHashTable(&H);
	for (i = 0; i<m; i++)
		InsertHash(&H, arr[i]);

	result = SearchHash(H, key, &p);
	if (result)
		printf("查找 %d 的地址为：%d \n", key, p);
	else
		printf("查找 %d 失败。\n", key);

	for (i = 0; i<m; i++)
	{
		key = arr[i];
		SearchHash(H, key, &p);
		printf("查找 %d 的地址为：%d \n", key, p);
	}

	return 0;
}

散列表查找性能分析

1.散列函数是否均匀

2.处理冲突的方法

3.散列表的装填因子

装填因子=填入表中的记录个数/散列表长度；装填因子标志散列表的装满程度。当填入表中的记录越多，装填因子越大，产生冲突的可能性越大。