哈希函数如何分配关键字

Question

typedef unsigned int Index;//用 Index 这个类型来表示数组下标，看起来更清晰
Index Hash(const char* key, int tablesize)//key：要处理的字符串（比如"张三"、"apple"），tablesize：哈希表的大小（数组长度）
{
    unsigned int hashval = 0;
    while (*key != '\0')
    {
        hashval += *key++;
    }
    return hashval % tablesize;
}

请问while语句块在这个代码有什么作用？

Answer 1

问题分析

哈希函数的作用是将给定的关键字（这里是字符串key）映射到哈希表的下标（由tablesize指定大小）。常见的哈希函数对于字符串的处理方式有多种，比如直接定址法、数字分析法、平方取中法、折叠法、除留余数法等，这里可以考虑使用除留余数法来实现简单的哈希函数分配关键字。

代码实现

typedef unsigned int Index;

Index Hash(const char* key, int tablesize) {
    unsigned int hashVal = 0;
    while (*key!= '\0') {  // 遍历字符串中的每个字符
        hashVal = (hashVal * 31 + *key) % tablesize;  // 除留余数法，这里使用31作为缩放因子
        key++;
    }
    return hashVal;
}

解释说明

1. 初始化哈希值：首先定义一个unsigned int类型的变量hashVal并初始化为0，用于存储计算得到的哈希值。
2. 遍历字符串：通过while循环遍历输入的字符串key，循环条件是字符没有到达字符串末尾（即*key!= '\0'）。
3. 计算哈希值：在循环内部，使用除留余数法来计算哈希值。具体公式为hashVal = (hashVal * 31 + *key) % tablesize。这里乘以31是一种常见的处理字符串哈希的方式，它可以较好地混合字符串中的各个字符信息，然后对tablesize取模，使得哈希值落在0到tablesize - 1的范围内，从而作为哈希表的下标。
4. 返回哈希值：最后将计算得到的哈希值返回。

总结结尾

以上代码实现了一个简单的基于除留余数法的哈希函数来分配字符串关键字到哈希表的下标。通过遍历字符串并逐步计算哈希值，最终得到适合哈希表大小的下标值。希望以上内容对你有帮助