字符串比较和哈希的区别

Question

14

我最近学习了滚动哈希数据结构，它的主要用途之一是在字符串中搜索子串。以下是我注意到的一些优点：

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

我的研究结果表明，子串越大，传统重新哈希方法运行所需的时间就越长（如预期），而滚动哈希运行非常快（如预期）。然而，相互比较子字符串的运行速度比滚动哈希快得多。这是为什么呢？

为了有所了解，假设函数在约240万个字符的字符串中搜索100个字符的子串的运行时间如下：

为什么字符串比较会比滚动哈希快那么多呢？这是否与JavaScript有关？在JavaScript中，字符串是一种原始类型；这会导致字符串比较以恒定时间运行吗？

我主要的困惑是JavaScript中字符串比较为何如此快速，当我认为它们应该相对较慢。

注：通过“字符串比较”，我指的是像stringA === stringB这样的内容

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

- Nick Zuber

1

你的滚动哈希实现是什么样子的？或许你可以在jsperf上设置它，这样我们就可以自己测试了。很可能你正在使用的JavaScript引擎在比较简单字符串方面比你能够编写的任何JavaScript代码都要快得多。 - adeneo

你可以编写自己的字符串比较函数，并将其与滚动哈希进行比较。 - jHilscher

我的滚动哈希实现可以在这里找到，然而主要问题是JavaScript中字符串比较的速度有多快。我认为字符串比较应该相对较慢，所以我很困惑它在JavaScript中为什么/如何如此快速。 - Nick Zuber

再次强调，这可能取决于具体的实现方式，比如在 C++ 等语言中引擎的编写方式会决定使用字符串时 ==、===、indexOf 等比较操作的内部速度。 - adeneo

@adeneo 如果你好奇的话，我已经找到了这个谜题的答案。 - Nick Zuber

1

太好了，这是一个很好的答案 +1 - adeneo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Zuber · Accepted Answer

在进行一些测试和分析后，我得出结论，与直接比较两个字符串相比，我的滚动哈希方法运行稍慢有几个原因。

如果滚动哈希声称可以在常数时间内运行，为什么它比比较字符串还要慢呢？

函数相对较慢 - 调用函数略慢于直接执行内联代码。在我的情况下，每次滚动哈希重新计算其内部窗口时，必须在对象上调用一个函数，因此花费的时间比字符串比较长，因为该代码只是内联代码。特别是在我的基准测试中，滚动哈希要在200万次迭代中进行“移位”，这种函数的减速效果更加明显。
但为什么字符串比较如此之快？

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

总之

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