title: String Comparison vs. Hashing
body: <p>I recently learned about the <a href="https://en.wikipedia.org/wiki/Rolling_hash" rel="noreferrer">rolling hash</a> data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed:</p>
  
  <ul>
  <li>Comparing two strings can be expensive so this should be avoided if possible</li>
  <li>Hashing the strings and comparing the hashes is generally much faster than comparing strings, however rehashing the new substring each time traditionally takes linear time</li>
  <li>A rolling hash is able to rehash the new substring in constant time, making it much quicker and more efficient for this task</li>
  </ul>
  
  <p>I went ahead and implemented a rolling hash in JavaScript and began to analyze the speed between a rolling hash, traditional rehashing, and just comparing the substrings against each other.</p>
  
  <p>In my findings, the larger the substring, the longer it took for the traditional rehashing approach to run (as expected) where the rolling hash ran incredibly fast (as expected). However, comparing the substrings together ran much faster than the rolling hash. How could this be?</p>
  
  <p>For the sake of perspective, let's say the running times for the functions searching through a ~2.4 million character string for a 100 character substring were the following:</p>
  
  <ul>
  <li><strong>Rolling Hash</strong> - 0.809 seconds</li>
  <li><strong>Traditional Rehashing</strong> - 71.009 seconds</li>
  <li><strong>Just comparing the strings (no hashing)</strong> 0.089 seconds</li>
  </ul>
  
  <p>How could the string comparing be so much faster than the rolling hash? Could it just have something to do with JavaScript in particular? Strings are a primitive type in JavaScript; would this cause string comparisons to run in constant time?</p>
  
  <p>My main confusion is as to how/why string comparisons are so fast in JavaScript, when I was under the impression that they were supposed to be relatively slow.</p>
  
  <p><strong>Note:</strong>
  By <em>string comparisons</em> I'm referring to something like <code>stringA === stringB</code></p>
  
  <p><strong>Note:</strong>
  I asked this question over on the <a href="https://cs.stackexchange.com/questions/51933/string-comparison-vs-hashing">Computer Science Community</a> and was informed that I should ask it here as well because this is most likely JavaScript specific.</p>