字符串hash函数 - skyli - C 博客

字符串hash函数，解决冲突用开放定址法，每次对哈希值加1
在下列程序中，不是按常规方法用哈希表来记录关键字，
而是用整型数组Htable记录关键字在字符串ch中的位置。
在插入时不用把关键字复制到哈希表中，只是记录一个索引，从而提高了效率。
当查询时，只要把Htable的值映射到字符串ch中就可以了。
注意ch的下标要从1开始，因为Htable中的零值认为是空，处理起来比较方便。

#include<iostream>
#include<string>
using namespace std;
const int MAXN = 9973; //哈希表长度
const int len = 30; //字符串的最大长度
int Htable[MAX];
char ch[MAX][len]; //存储关键字的字符串
unsigned long Hash(char * key)
{
    unsigned long h = 0;
    while(*key)
    {
        h = (h << 4) + *key++;
        unsigned long g = h & 0xf0000000L;
        if(g)
            h ^= g >> 24;
        h &= ~g;
    }
    return h % MAX;
}
int search(char * key)
{
    unsigned long i = Hash(key);
    while(Htable[i])
    {
        if(strcmp(ch[Htable[i]], key) == 0)
            return i;
        i = (i + 1) % MAX;
    }
    return -1;
}
int insert(char * key, int j) //j为关键字在ch中的位置，即索引
{
    unsigned long i = Hash(key);
    while(Htable[i])
        i = (i + 1) % MAX;
    Htable[i] = j;
    return i;
}

posted on 2007-04-07 16:22 beyonlin 阅读(911) 评论(2)  编辑 收藏 引用 所属分类: acm之路 、C++之路

FeedBack:

# re: 字符串hash函数 2007-07-04 00:45 原来如此

请教：在insert函数中，key的值没有存到ch组里面去吧？

int insert(char * key, int j) //j为关键字在ch中的位置，即索引
{
unsigned long i = Hash(key);
while(Htable[i])
i = (i + 1) % MAX;
Htable[i] = j;
return i;