散列/散列函数「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

散列是一种用于以常数平均时间执行插入、删除和查找的技术。

每个关键字被映射到从0-TableSize-1这个范围中的某个数，并且被放到适当的单元中。这种映射就叫做散列函数

我认为，先用散列函数将我们所要进行操作的集合整合成散列表，是对之后的操作的一种便利。放到实际中去，我们要进行操作的集合不仅仅只是数字，例如图书馆中的书籍分类等等。而且就算是一组不连续差距较大的数字，要执行后序的插入删除和查找都是很不方便的。我们可以通过某种规定，将每个关键字放到合适的为止上去，编写散列函数。但是难免会遇到两个关键词被单列到同一个值的情况，（称为冲突），如何解决冲突是一个很关键的问题，之后另开博。

对于一般的数字，可以通过模运算

一个简单的代码实现如下（不涉及冲突）

#include<stdio.h>

int main()
{
    //自定义数组，存放初始的数字集合 
    int a[9] = {
  
  22,23,25,21,20,27,24,28,26};
    int b[9];
    int i;
    for(i = 0; i < 9; i++)
    {
        b[a[i]%10] = a[i];   //通过模10运算，将关键字散列合适的位置 
    }
    for(i = 0; i < 9; i++)   //输出散列表 
    printf("%d ", b[i]);
    return 0;
} 

输出结果如图

如果关键字是字符串，另一个很容易想到的办法是将字符中的ASCII码值加起来
伪代码如下：

Index
Hash(const char *key, int TableSize)
{
    unsigned int HashVal = 0;
    while(*key != '
Index
Hash(const char *key, int TableSize)
{
unsigned int HashVal = 0;
while(*key != '\0')   //循环将字符中的ASCII值加起来
HashVal += *key++;
return HashVal % TableSize;  //对TableSize取余并返回其值
}
')   //循环将字符中的ASCII值加起来
        HashVal += *key++;
    return HashVal % TableSize;  //对TableSize取余并返回其值
}

虽然这种方法简单又很容易得到答案，但是对于很大的表，此函数并不会很到的分配关键字。设所有关键字最多8个字符长，由于char类型的值最多是127，因此这个散列函数之恩那个取值在0到27*8之间，若TableSize超过了1w，显然这并不是一种均匀的分配。