字符串比较与散列

Question

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

• 比较两个字符串可能会很昂贵，因此应尽可能避免这种情况
• 散列字符串和比较散列通常比比较字符串快得多，但是每次重新散列新的子字符串传统上需要线性时间
• 滚动散列能够在恒定时间内重新散列新的子字符串，使其更快、更有效地完成这项任务

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

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

为方便起见，假设在大约 240 万个字符串中搜索 100 个字符的子字符串的函数的运行时间如下：

• 滚动哈希- 0.809 秒
• 传统 Rehashing - 71.009 秒
• 仅比较字符串（无散列） 0.089 秒

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

我的主要困惑是关于在 JavaScript 中字符串比较如何/为什么如此之快，当时我的印象是它们应该相对较慢。

注意： 通过字符串比较，我指的是类似的东西stringA === stringB

注意： 我在计算机科学社区上问过这个问题，并被告知我也应该在这里问这个问题，因为这很可能是 JavaScript 特定的。

Answer 1

经过一些测试和分析，我得出的结论是，为什么我的滚动散列方法比简单地比较两个字符串运行速度稍慢，有几个原因。

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

  函数相对较慢——调用函数比简单地执行内联代码稍慢。在我的特殊情况下，每次滚动哈希重新散列其内部窗口时都必须在我的对象上调用一个函数，因此与字符串比较相比，运行时间略长，因为该代码只是内联的。特别是因为我的基准测试有超过 200 万次迭代的滚动哈希“移位”，可以更清楚地看到这个函数的减速。

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

  字符串是原始的——基本上，因为字符串是 JavaScript 中的原始类型，尝试比较两个字符串很可能会调用一些直接在解释器中编码的例程。这种低级评估可以尽可能快地完成（类似于比较数字）。

综上所述

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