散列表的基本概念
假设某应用要用到一个动态集合,其中每个元素都有一个属于[0..p]的关键字,此处p是一个不太大的数,且没有两个元素具有相同的关键字,则可以用一个数组[p+1]存储该动态集合,并且使用关键字作为数组下标进行直接寻址。这一直接寻址思想在前面的非比较排序中就有所应用。然而,当p很大并且实际要存储的动态集合大小n<<p时,这样一个数组将浪费大部分空间。
散列表(Hash table),使用具有m个槽位的数组来存储大小为n的动态集合。α=n/m被定义为散列表的装载因子。在散列表中,具有关键字k的元素的下标为h(k),即利用散列函数h,根据关键字k计算出槽的位置。散列函数h将关键字域[0..p]映射到散列表[0..m-1]的槽位上,这里,m可以远小于p,从而缩小了需要处理的下标范围,并相应地降低了空间开销。散列表带来的问题是:两个关键字可能映射到同一个槽上,这种情形称为碰撞。因此,散列函数h应当将每个关键字等可能地散列到m个槽位的任何一个中去,并与其它关键字已被散列到哪一个槽位中无关,从而避免或者至少最小化碰撞。
散列函数
多数散列函数都假定关键字域为自然数集。如果所给关键字不是自然数,则必须有一种方法将它们解释为自然数。这里,介绍几种主要的散列函数:
(1)平方取中法
具体方法:先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关,所以由此产生的散列地址较为均匀。
【例】将一组关键字(0100,0110,1010,1001,0111)平方后得(0010000,0012100,1020100,1002001,0012321)
若取表长为1000,则可取中间的三位数作为散列地址集:(100,121,201,020,123)。
相应的散列函数用C实现很简单:
int Hash(int key){ //假设key是4位整数
key*=key; key/=100; //先求平方值,后去掉末尾的两位数
return key%1000; //取中间三位数作为散列地址返回
}
(2)除余法
该方法是最为简单常用的一种方法。它是以表长m来除关键字,取其余数作为散列地址,即 h(key)=key%m
该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。
【例】若选m是关键字的基数的幂次,则就等于是选择关键字的最后若干位数字作为地址,而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
【例】若关键字是十进制整数,其基为10,则当m=100时,159,259,359,…,等均互为同义词。
(3)相乘取整法
该方法包括两个步骤:首先用关键字key乘上某个常数A(0<A<1),并抽取出key.A的小数部分;然后用m乘以该小数后取整。即:
该方法最大的优点是选取m不再像除余法那样关键。比如,完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用,但对某些值效果会更好。Knuth建议选取
该函数的C代码为:
int Hash(int key){
double d=key *A; //不妨设A和m已有定义
return (int)(m*(d-(int)d));//(int)表示强制转换后面的表达式为整数
}
(4)随机数法
选择一个随机函数,取关键字的随机函数值为它的散列地址,即h(key)=random(key),其中random为伪随机函数,但要保证函数值是在0到m-1之间。
解决碰撞的方法
解决碰撞的方法主要有两种:链接法和开放寻址法。
l链接法(chaining):把散列到同一槽中的所有元素都存放在一个链表中。每个槽中有一个指针,指向由所有散列到该槽的元素构成的链表的头。如果不存在这样的元素,则指针为空。如果链接法使用的是双向链表,那么删除操作的最坏情况运行时间与插入操作相同,都为O(1),而平均情况下一次成功的查找需要Θ(1+α)时间。
l开放寻址法(open addressing):所有的元素都存放在散列表中。因此,适用于动态集合大小n不大于散列表大小的情况,即装载因子不超过1。否则,可能发生散列表溢出。在开放寻址中,当要插入一个元素时,可以连续地探查散列表的各项,直到找到一个空槽来放置待插入的关键字。探查的顺序不一定是0, 1, …, m-1,而是要依赖于待插入的关键字k。于是,将探查号作为散列函数的第二个输入参数。为了使所有的槽位都能够被探查到,探查序列<h(k,0), h(k,1), …,
h(k,m-1)>必须是<0, 1, …, m-1>的一个排列。有三种技术常用来计算开放寻址法中的探查序列:线性探查、二次探查,以及双重探查。
l线性探查(linear probing):使用的散列函数如下
h(k,i) = (h’(k) + i) mod m, i=0, 1, …, m-1
|
h’为一个普通的散列函数,见前面的介绍。线性探查存在一个称为一次群集的问题,即随着时间的推移,连续被占用的槽不断增加,平均查找时间也随着不断增加。但是,线性探查的优点在于,对m的取值没有特殊的要求。
l二次探查(quadratic probing):使用的散列函数如下
h(k,i) = (h’(k) +c1 i + c2 i2) mod m, i=0, 1, …, m-1
|
为了能够充分利用散列表,c1、c2和m的值要受到限制。一种好的选择是,m为2的某个幂次(m=2p),c1=c2=1/2。二次探查,不会顺序地探查每一个槽位,解决了一次群集问题。但是,如果两个关键字的初始探查位置相同,那么它们的探查序列也是相同的,这一性质导致一种程度较轻的群集现象,称为二次群集。
l双重散列(double hashing):使用的散列函数如下
h(k,i) = (h1(k) + i h2(k)) mod m, i=0, 1, …, m-1
|
为能查找整个散列表,值h2(k)要与表的大小m互质。确保这一条件成立的一种方法是取m为2的幂,并设计一个总能产生奇数的h2。另一种方法是取m为质数,并设计一个总是产生较m小的正整数的h2。例如,可以取m为质数,h2(k)=1+(k
mod m’),m’=m-1。
完全散列
如果某一种散列技术在进行查找时,其最坏情况内存访问次数为O(1)的话,则称其为完全散列(perfect hashing)。通常利用一种两级的散列方案,每一级上都采用全域散列。为了确保在第二级上不出现碰撞,需要让第二级散列表Sj的大小mj为散列到槽j中的关键字数nj的平方。如果利用从某一全域散列函数类中随机选出的散列函数h,来将n个关键字存储到一个大小为m=n的散列表中,并将每个二次散列表的大小置为mj=nj2
(j=0, 1, …, m-1),则在一个完全散列方案中,存储所有二次散列表所需的存储总量的期望值小于2n。
附:链接法实现的散列表
#include <stdio.h>
#include <stdlib.h>
#include "chain_hash.h"
#define HASH_CONSTANT 0.6180339
typedef struct node
{
int key;
struct node *prev;
struct node *next;
}chain_hash_node;
chain_hash_node *new_chain_hash_table(int hash_table_size)
{
int i;
chain_hash_node *chain_hash_table;
chain_hash_table = malloc(sizeof(chain_hash_node)*hash_table_size);
for(i=0; i<hash_table_size; i++)
{
chain_hash_table[i].key = 0;
chain_hash_table[i].prev = NULL;
chain_hash_table[i].next = NULL;
}
return chain_hash_table;
}
void free_chain_hash_table(chain_hash_node *chain_hash_table, int hash_table_size)
{
int i;
chain_hash_node *node;
for(i=0; i<hash_table_size; i++)
{
while(chain_hash_table[i].next != NULL)
{
node = chain_hash_table[i].next;
chain_hash_delete(chain_hash_table[i].next);
free(node);
node = NULL;
}
}
free(chain_hash_table);
chain_hash_table = NULL;
}
void chain_hash_delete(chain_hash_node *node)
{
node->prev->next = node->next;
if(node->next != NULL)
node->next->prev = node->prev;
}
int chain_hash_func(int hash_table_size, int value)
{
return (hash_table_size * ((value*HASH_CONSTANT)-(int)(value*HASH_CONSTANT)));
}
void chain_hash_insert(chain_hash_node *chain_hash_table,int hash_table_size, int value)
{
int index;
chain_hash_node *node;
index = chain_hash_func(hash_table_size, value);
node = malloc(sizeof(chain_hash_node));
node->key = value;
node->prev = &chain_hash_table[index];
if(chain_hash_table[index].next != NULL)
chain_hash_table[index].next->prev = node;
node->next = chain_hash_table[index].next;
chain_hash_table[index].next = node;
}
chain_hash_node *chain_hash_search(chain_hash_node *chain_hash_table,int hash_table_size, int value)
{
int index;
chain_hash_node *node;
index = chain_hash_func(hash_table_size, value);
node = chain_hash_table[index].next;
while(node != NULL)
{
if(node->key == value)
return node;
node = node->next;
}
return NULL;
}
void chain_hash_print(chain_hash_node *chain_hash_table,int hash_table_size)
{
int i;
chain_hash_node *node;
printf("/nchain_hash_table:");
for(i=0; i<hash_table_size; i++)
{
printf("/nslot %d: ", i);
node = &chain_hash_table[i];
while(node != NULL)
{
printf("%d ", node->key);
node = node->next;
}
}
printf("/n/n");
}
分享到:
相关推荐
散列表的设计与实现,课程设计. 设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用...
为小于n个关键字设计一个散列表,使得查找成功时平均查找长度,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放定址法的线性探测法处理冲突。 1.从键盘输入关键字个数n及...
散列表的设计与实现,课程设计. 设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用...
设计散列表实现电话号码查找系统。基本要求:(1)设每个记录有下列数据项:电话号码、用户名、地址;(2)从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;(3)采用双散列法解决冲突;(4)查找并显示给定...
散列表是一种存储结构,是和链表,数组不同的存储结构,其存储位置是有存储数据而定的,本题中,有学生姓名、住址和电话号码,输入学生姓名,将拼音字母转化成阿克斯码,将所有的阿克斯码加起来与20取余数得到的数字...
散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置的表。 哈希函数的构造方法:1)...
5、散列表的设计与实现 任务:设计散列表实现电话号码查找系统。 要求: (1) 设每个记录有下列数据项:用户名、电话号码、地址; (2) 从键盘输入各记录,以用户名(汉语拼音形式)为关键字建立散列表; (3) ...
散列表散列表散列表散列表散列表散列表散列表散列表散列表散列表
Linux内核的实现,大量使用了数据结构,包括了数组、链表和散列表。其中用的最多的是双向循环链表。Linux内核使用的是自己定义的链表和散列表,简单而高效,使用方法也非常的别具一格。 研究Linux内核的链表和散...
数据结构课程设计,用散列表实现电话号码添加、查询,java语言,附软件截图,课程设计报告。
基本要求: (1)设每个记录有下列... (2)从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; (3)采用一定的方法解决冲突; (4)查找并显示给定电话号码的记录; (5)查找并显示给定用户名的记录。
数据结构课程设计 散列表的应用:插入买票
散列的C语言实现:链地址法、线性探测法、双重散列表
散列表在进行映射的时候经常会发生冲突,这里采用链接法来解决链接法映射冲突带来的问题
数据结构散列表编写的电话本及冲突处理源码,散列表,哈希表,存储数据,电话本,散列表,哈希表,存储数据,电话本
数据结构课程设计报告 题目1:基于散列表的程序相近度检测系统 ——采用的方法:哈希散列函数,二分查找 题目2:旅游交通查询系统 ——采用的方法:二维链表与图
设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用一定的方法解决冲突; 4) 查找并...
在cuda上用gpu实现散列表 在cuda上用gpu实现散列表
一个用c语言编写的散列表通讯录系统,实现了增删改查功能。