/*
* =====================================================================================
*
* Filename: hash.c
*
* Description: hash表
* Author: cdutyangshaokun@163.com
* =====================================================================================
*/
hash table 又称散列表，是一种线性存储结构。
hash的基本思想是：设要存储的对象个数为n，设置一个长度为m(m>=n)的连续内存单元，以线性表中的每个对象的关键字ki(0=<i<n-1)为自变量，通过一个哈希函数的函数h(ki),把ki映射为内存单元的地址，并把该对象存储在这个内存单元中。h(ki)也称为哈希地址。
哈希冲突：对于两个关键字ki和kj(i!=j),有ki！=kj，但是有h(ki)=h(kj).
同常把具有不同关键字而具有相同哈希地址的对象称为“同义词”，由同义词引起的冲突称为同义词冲突。
哈希函数的构造方法：
1： 直接地址法：
直接地址法是以关键字k本生或关键字加上某个数值常量c作为哈希地址的方法。
h(k)=k+c
这种方法简单，当关键字的分布基本连续时，可用直接地址法的哈希函数，否则，若关键字分布不连续将造成内存单元的大量浪费。
2：除留余数法：
用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法
h(k)=k%p
p应该取不大于m的素数效果最好。
3：数字分析法：
提取关键字中取值教均匀的数字位作为哈希地址的方法。
哈希冲突解决的办法：
基本思想是当发生哈希冲突时通过哈希冲突函数产生一个新的哈希地址使hl(ki)!=
hl(kj),哈希冲突函数产生的哈希地址仍可能有哈希冲突问题，此时，在用一个新
的哈希冲突函数得到新的哈希地址，一直到不存在哈希冲突为止。
1：开放地址法：哈希空闲单元既向同义词关键字开发，也向发生冲突的非同义词开放。
a：线性探查法：
从发生冲突的地址开始，依次探查d的下一个地址，直到找到一个空闲地址为止，公式描述为：
d0=h(k);
di=(di+1)modm (1<<i<<m-1)
b:平方探查法：
d0=h(k);
2
di=(d0+i )mod m (1<<i<<m-1)
缺点：不能探查到哈希表上的所有单元，但是至少能探查到一半的单元。
2：拉链法：
拉链法是把所有的同义词用单链表链接起来的方法，在这中方法中，哈希表每个单元存放的不再是记录本身，而是相应同义词单链表的头指针。
哈希表的运算：
哈希表的目的主要是用于快速查找，且插入和删除均要用到查找操作。
以下是有关的类型说明：
#define maxsize 100 /*定义最大哈希表的长度*/
#define NULLKEY -1 /*定义空关键值*/
#define DELKEY -2 /*定义被删除关键字值*/
typedef int keytype;
typedef char * infotype;
typedef struct
{
keytype key;
infotype data;
int count;
}hashtable[maxsize];
1:哈希表的查找：
哈希表的查找和建表过程类似，假设给定的值是k，根据建表是设定的散列函数h，计算出哈希地址h(k),若表中该地址单元不为空，且该地址的关键字不等于k，则按建表时设定的处理冲突的方法找下一个地址。
int searchht(hashtable ha,int p,keytype k)
{
int i=0;
int adr;
adr=k%p;/*我们这里用的是除留余数法来构建的hash表*/
while(ha[adr].key!=NULLKEY&&ha[adr].key!=k)
{
i++;
adr=(adr+1)%p;
}
if(ha[adr],key==k)
{
return adr;
}
else
return -1;
}
2:删除
采用开放地址法处理冲突的哈希表上执行删除操作，只能在被删除记录上做删除标记，而不能真正删除。
int deleteht(hashtable ha,int p,int k,int &n)/*删除哈希表中的关键字k*/
{
int adr;
adr=searchht(ha,p,k);
if(adr!=-1)
{
ha[addr].key=DELKEY;
n--；/*哈希表的长度减1*/
return 1;
}
else
return 0;
}
3:建表和插入
建表是首先要将表中的个各节点的关键字清空，使其地址为开放的，让后调用插入算法将给定的关键字序列依次插入表中，插入算法首先调用查找算法，若在表中找到代插入的关键字，则插入失败，若在表中找到一个开放的地址，则将代插入的节点插入其中。
void insertht(hashtable ha,int &n,keytype k,int p)
{
int i,adr;
adr=k%p;
if(ha[adr].key==NULLKEY||ha[adr].key==DELKEY)
{
ha[adr].key=k;
ha[adr].count=1;
}
else
{
i=1;
do
{
adr=(adr+1)%p;
i++;
}while(ha[adr].key!=NULLKEY&&ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
void creatht(hashtable ha,keytype x[],int n,int m,int p)
{
int i,n1=0;
for(i=0;i<m;i++)
{
ha[i].key=NULLKEY;
ha[i].count=0;
}
for(i=0;i<n;i++)
{
insertht(ha,n1,x[i],p);/*调用插入算法在ha中插入x[i].*/
}
}
问题描述：
根据本书提供的Linux内核list.h头文件，实现一个带哈希链表功能的程序。其中宿主节点hlist_node仅包含一个数据成员char *name，要求能完成根据给定的字符串，在该哈希链表中进行宿主节点的查找匹配、增加和删除。
程序如下：
/*
* =====================================================================================
*
* Filename: hash_oper.c
*
* Description: 哈希表的操作
*
* Version: 1.0
* Created: 2010年11月07日 15时39分29秒
* Revision: none
* Compiler: gcc
*
* Author: Yang Shao Kun (), cdutyangshaokun@163.com
* Company: College of Information Engineering of CDUT
*
* =====================================================================================
*/
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include"list.h"
#define maxsize 15 /*定义最大哈希表的长度 */
#define NULLKEY -1 /*定义空关键字的值 */
#define DELKEY -2 /*定义被删除关键字的值 */
#define NULL ((void *)0)
struct hashtable {
char *name;
struct hlist_node node;
};
/*一个简单的hash函数*/
unsigned int BKDhash(char *str)
{
unsigned int send = 131;
unsigned int hash = 0;
while (*str) {
hash = hash * send + (*str++);
}
return (hash & 0x7fffffff);
}
void my_hlist_entry(struct hlist_node *pos, struct hlist_head *head);
void print(int n, struct hashtable ha[]);
int main(int argc, char *argv[])
{
int i;
int adr, t;
struct hlist_head *p, *head;
struct hlist_node *pos;
struct hashtable my_hashtable[maxsize];
struct hashtable *temp;
struct hashtable *ptr1, *ptr;
char string[11] =
{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', '/0' };
/*初始化 */
for (i = 0; i < maxsize; i++)
INIT_HLIST_NODE(&my_hashtable[i].node);
for (i = 0; i < maxsize; i++) {
my_hashtable[i].name = NULL;
}
head = (struct hlist_head *) malloc(sizeof(struct hlist_head));
INIT_HLIST_HEAD(head);
p = head;
for (i = 0; string[i] != '/0'; i++) {
adr = BKDhash(&string[i]);
adr = adr & maxsize;
if ((my_hashtable[adr].name) == NULL) {
if (i == 0 && my_hashtable[adr].name == NULL) {
my_hashtable[adr].name = &string[i];
hlist_add_head(&(my_hashtable[adr].node),
head);
pos = &(my_hashtable[adr].node);
} else {
(my_hashtable[adr].name) = &string[i];
hlist_add_after(pos,
&(my_hashtable[adr].node));
pos = pos->next;
}
} else {
do {
adr = (adr + 1) & maxsize;
} while (my_hashtable[adr].name != NULL);
(my_hashtable[adr].name) = &string[i];
hlist_add_after(pos, &(my_hashtable[adr].node));
pos = pos->next;
}
}
/*打印hash */
printf
("遍历整个链表的顺序，并输出到屏幕，使用 hlist_for_each()/n");
my_hlist_entry(pos, head);
printf("/n");
/*节点的对应的数组下标---哈希值，和对应节点存放的字符 */
printf("元素对应的数组下标为：/n");
print(maxsize, my_hashtable);
/*查找和插入的实现,如是 字符 c,并在该宿主节点后加入新节点，元素为s */
printf
("我们查找数据元素为字符‘c’的节点，并在节点后面加入数据元素为字符‘s’的节点/n");
char arr = 's';
hlist_for_each(pos, p) {
temp = hlist_entry(pos, struct hashtable, node);
if (temp->name == &string[2]) {
printf("find 'c'/n");
adr = BKDhash(&arr);
adr = adr & maxsize;
if ((my_hashtable[adr].name) == NULL
|| *(my_hashtable[adr].name) == DELKEY) {
my_hashtable[adr].name = &arr;
hlist_add_before(&my_hashtable[adr].node,
&temp->node);
} else {
do {
adr = (adr + 1) & maxsize;
} while (my_hashtable[adr].name != NULL
&& *(my_hashtable[adr].name) !=
DELKEY);
my_hashtable[adr].name = &arr;
hlist_add_before(&my_hashtable[adr].node,
&temp->node);
}
printf
("插入节点后，元素对应的下标为：/n");
print(maxsize, my_hashtable);
printf
("插入新节点后，链表顺序变为：/n");
break;
}
}
my_hlist_entry(pos, head);
printf("/n");
/*节点的删除，现在我们来删除刚才添加的节点 */
/*首先调用查找，查找节点，s */
hlist_for_each(pos, p) {
temp = hlist_entry(pos, struct hashtable, node);
if (temp->name == &arr) {
printf("find s,then delete it/n");
hlist_del_init(pos);
/*我们b不free掉内存，只是做一个标记，表示已经删除 */
*((*temp).name) = DELKEY;
}
}
print(maxsize, my_hashtable);
printf("删除该节点后，链表遍历/n");
my_hlist_entry(pos, head);
printf("/n");
return 0;
}
void print(int n, struct hashtable ha[maxsize])
{
int i;
for (i = 0; i < n; i++) {
if ((ha[i].name) != NULL && *(ha[i].name) != DELKEY) {
printf("---%d--->%c/n", i, *(ha[i].name));
}
}
}
void my_hlist_entry(struct hlist_node *pos, struct hlist_head *head)
{
struct hashtable *temp;
hlist_for_each(pos, head) {
temp = hlist_entry(pos, struct hashtable, node);
printf("->%c", *(temp->name));
}
}