巨佬的hash讲解pdf，讲的非常好！！！我看一遍就会了

哈希（Hash）是计算机科学中的一种基本算法，用于将任意长度的输入（预映射pre-image）通过散列函数转换为固定长度的输出，即散列值（Hash值）。散列值通常用来快速检索数据结构中的项目，例如在哈希表中。散列的概念基于将一个“大”数据集合映射为一个小得多的数据集合，以减少数据存储空间和加快数据检索速度。 在讨论字符串匹配的上下文中，哈希算法可以用于快速检测两个字符串或子串是否相等。在给定的文件内容中，介绍了基于哈希的字符串处理技术。文档提到了一种简化哈希算法，其中假设字符集只有26个小写英文字母，并且将其映射到一个较小的数列。 哈希算法通常包括以下关键步骤： 1. 字符映射：将字符串中的每个字符转换成一个整数（例如，'a'映射为1, 'b'映射为2，依此类推）。 2. 进制选择：选择一个数字作为数列的进制（base），例如，如果选择27作为进制，那么每个字符映射后的数列就可以表示为27进制下的数字。 3. 散列计算：通过数学运算，将映射后的整数序列转换为一个整数，即散列值。这通常涉及到前缀和（前缀的累加和）和进制转换的计算。 4. 子串哈希：为了在O(1)时间内得到任意子串的哈希值，可以事先计算字符串每个前缀的哈希值，并存储起来。查询时，直接从存储的哈希值中计算所需子串的哈希值。 文档中提到了三种计算机实现哈希的方式： 1. 溢出处理：如果哈希值的计算结果超出了存储数据类型的最大范围，那么可以选择不处理溢出，即自然溢出。在C++中，如果使用unsigned long long类型进行计算，那么一旦运算结果超出了其最大表示范围，就会自动溢出并折回。 2. 自然溢出（Rolling Hash）：这种方法利用了计算机硬件的特性，让数据在溢出时自动折回，不需要对数据进行特别的溢出处理。具体而言，当计算机尝试存储超出其存储范围的数据时，结果会按照特定的模运算折回一个较小的范围内。例如，如果使用64位无符号整数存储，其最大值为2^64-1，那么计算时超出这个范围的结果会自动折回到0开始的范围内。 3. 手动溢出：如果需要精确的哈希值并且不希望溢出，可以使用模运算来防止结果溢出。例如，通过模上一个大素数（通常称为模数），可以得到一个有限范围内的哈希值，这个方法在某些哈希算法实现中非常常见，比如Rabin-Karp算法。 文档中提供的代码片段表明，在预处理字符串阶段，可以在O(n)时间内（n是字符串的长度）计算所有前缀的哈希值，然后再O(1)时间内计算任意子串的哈希值。这样，在需要多次比较字符串子串的场景下（例如在字符串匹配算法中），可以显著提高效率。 需要注意的是，哈希函数设计需要尽量避免哈希冲突，即不同输入得到相同哈希值的情况。在实际应用中，完美的哈希函数是不存在的，但设计者会尽量减少冲突的概率。在某些情况下，例如使用哈希表进行快速查找时，冲突会导致查找效率下降。 总结来说，哈希算法是一种非常强大的数据处理工具，广泛应用于数据检索、密码学、算法设计等领域。上述文档中的内容提供了关于如何设计和实现一个字符串哈希函数的基础知识，并对可能遇到的溢出处理问题提出了解决方案。