Thomas Wang 整数与字符串Hash算法实现

本文主要介绍了两种哈希算法：Thomas Wang的整数哈希算法和基于字符串的哈希算法，包括加法哈希、旋转哈希和逐位哈希方法。 在计算机科学中，哈希（Hash）算法是一种将任意长度的数据映射为固定长度输出的函数，通常用于快速查找、数据验证和加密等领域。哈希算法的特点是输入数据的微小变化会导致输出哈希值的巨大差异，使得相同的输入会产生相同的哈希值，而不同的输入则尽可能产生不同的哈希值。 Thomas Wang的整数哈希算法是一种高效的哈希计算方法，适用于整数。在提供的代码中，没有找到具体的Thomas Wang整数哈希算法，但提到了两种字符串哈希算法： 1. **加法哈希（Additive Hash）**： - 这个算法通过对字符串中的每个字符进行累加求和，然后对一个素数`prime`取模来计算哈希值。 - 算法步骤：初始化`hash`为字符串长度，遍历字符串，将每个字符的ASCII码值累加到`hash`中，最后返回`hash % prime`的结果。 - 使用素数`prime`可以减少哈希冲突，提高哈希表的性能。 2. **旋转哈希（Rotating Hash）**： - 这种算法利用位操作（左移、右移）来改变哈希值，增加了哈希算法的均匀性。 - 算法步骤：初始化`hash`为字符串长度，遍历字符串，对每个字符进行位操作（左移4位，右移28位）并异或操作，最后同样对`prime`取模。 - 变体中还包括了对`hash`进行位操作（右移10位和20位）后再进行异或，以进一步提高分布的均匀性。 3. **逐位哈希（One-by-One Hash）**： - 逐位哈希是一种常见的字符串哈希算法，它通过逐步累加字符，并结合位操作来生成哈希值。 - 算法步骤：初始化`hash`为0，遍历字符串，每次累加当前字符的ASCII码值，然后通过位操作增加复杂性（左移10位，异或，右移6位等），最后再次进行位操作和累加。 - 此算法通过位运算来确保哈希值的变化更为复杂，降低碰撞概率。 这些哈希算法的目的是在有限的哈希空间中尽可能地分散输入数据，从而在数据结构如哈希表中实现高效查找。选择哪种哈希算法取决于具体的应用场景，如数据的特性、内存限制以及对冲突的容忍度。在实际应用中，还需要考虑哈希函数的实现效率和哈希表的负载因子，以确保系统的性能和稳定性。