数据结构中的哈希函数

在数据结构中，哈希函数是将输入数据映射到哈希表的索引或地址的一种函数。它将数据转换为固定长度的哈希值，并将其存储在哈希表中。哈希函数通常使用散列算法来生成哈希值。

哈希函数有以下特点：

1. 可以快速计算出哈希值；
2. 哈希函数应该尽可能避免哈希冲突；
3. 对于相同的输入，哈希函数应该始终生成相同的哈希值；
4. 对于不同的输入，哈希函数应该生成不同的哈希值。

常见的哈希函数有以下几种：

1. 直接寻址法：将关键字作为数组下标，直接存储在对应位置上；
2. 数字分析法：根据数据分析出的特征来构造哈希函数；
3. 平方取中法：先将关键字平方，然后取出中间若干位作为哈希值；
4. 折叠法：将关键字划分为几段，然后将这几段相加得到哈希值；
5. 随机数法：随机选择一些系数，将关键字与系数相乘，然后取模得到哈希值。