C++字符串Hash与数值Hash解析

"这篇资源主要讨论了C++中关于字符串Hash和数值Hash的重要知识，由清华大学及成都七中(高新)的杨雅儒分享。它介绍了如何计算字符串和数值的Hash值，以及如何处理Hash冲突，并给出了三个典型的应用问题及其解决方案。" 在C++编程中，Hash是一种常用的数据结构和算法技术，主要用于快速查找和比较数据。在这个主题中，学长提到了两种主要类型的Hash：字符串Hash和数值Hash。 1. 字符串Hash：字符串Hash的基本思想是将一个字符串转换为一个单一的数值，这个数值称为Hash值。在实际应用中，通常选择无符号长整型(unsigned long long)作为存储类型，允许在溢出时自然截断。为了避免模运算，可以采用“自然溢出”策略。选取一个较大的质数作为base，比如计算字符串的前缀Hash值pre[i]，其中pre[i]等于各个字符乘以base的对应幂次并累加。这种方法虽然可能导致不同的字符串得到相同的Hash值（哈希冲突），但在大多数情况下，这种冲突的概率非常小。 2. 数值Hash：数值Hash是将大的数值转化为较小的Hash值。由于需要减少的位数较多，冲突的可能性会增大。一种简单的处理方法是对原始数值直接取模。当遇到冲突时，可以通过跳跃法解决，即在哈希表中向后移动一定的步长t，直到找到未被占用的位置或原始值匹配。 学长还通过三个问题展示了Hash在实际问题中的应用： - Problem1-1：给定两个字符串A和B，求A在B中的出现次数。通过计算A的Hash值和B的前缀Hash数组，可以快速比较子串并进行计数。 - Problem1-2：对于一组正整数和查询，判断查询的整数是否在给定集合中。利用Hash表存储这些数字，可以实现快速的查询操作，避免每次都遍历整个数组。 - Problem1-3：处理一个n*m的01矩阵，对多个A*B大小的01矩阵进行询问，判断它们是否出现在原始矩阵中。这个问题可以通过扩展字符串Hash的思想，构建一个二维的Hash值系统来解决。 理解和熟练掌握Hash技术对于C++程序员来说至关重要，因为它在算法设计和数据结构优化中扮演着重要角色，能够显著提高程序的效率。在实际编程中，根据具体问题选择合适的Hash策略和处理冲突的方法是解决问题的关键。