字符串比较与哈希

String Comparison vs. Hashing

我最近了解了 rolling hash 数据结构，基本上它的主要用途之一是搜索字符串中的子字符串。以下是我注意到的一些优点：

我继续在 JavaScript 中实现了滚动哈希，并开始分析滚动哈希、传统重新哈希和仅将子字符串相互比较之间的速度。

在我的发现中，子字符串越大，传统的重新散列方法 运行（如预期）花费的时间越长，其中滚动散列 运行 非常快（如预期）。但是，将子字符串一起比较 运行 比滚动散列快得多。怎么会这样？

为了直观起见，假设函数在约 240 万个字符串中搜索 100 个字符的子字符串的 运行ning 次如下：

字符串比较怎么会比滚动哈希快这么多？它会不会特别与 JavaScript 有关？字符串是 JavaScript 中的原始类型；这会导致字符串在恒定时间内与 运行 进行比较吗？

我的主要困惑是 how/why 字符串比较在 JavaScript 中如此之快，而我的印象是它们应该相对较慢。

注： 通过 字符串比较 我指的是 stringA === stringB

注： 我在 Computer Science Community 上问过这个问题，并被告知我也应该在这里问这个问题，因为这很可能是 JavaScript 具体的。

经过一些测试和分析，我得出的结论是，有几个原因导致我的滚动哈希方法 运行ning 比简单地比较两个字符串稍微慢一些。

  • 如果滚动哈希在恒定时间内声称运行，它怎么会比比较字符串慢？

    函数相对较慢 - 调用函数比简单地executing code inline稍慢。在我的特殊情况下，一个 每次滚动哈希时都必须在我的对象上调用函数 重新哈希其内部 window，因此需要稍长的时间才能 运行 与字符串比较相比，因为该代码只是内联的。特别是因为我的基准测试有超过 200 万次迭代的滚动哈希 "shift"，这个函数变慢可以更清楚地看到。

  • 但是为什么字符串比较这么快？

    字符串是原始的 - 基本上，因为 strings are a primitive type in JavaScript，尝试比较两个字符串将最 可能会调用一些直接在 口译员。这种低水平的评估可以像 体系结构可能可以（类似于比较数字）。

总结

在这种情况下，比较 JavaScript 中的字符串最终会比滚动哈希更快，因为字符串是 原始的 ，因此允许解释器使用这些元素非常快，因为简单地 调用函数会产生轻微的开销 并在很小的范围内减慢进程。