字符串哈希---帮助你操作字符的强大算法

字符串哈希是一种将字符串转化为哈希数字的技术。为什么我们需要它？有时候比较大的字符串，不需要比较字符串可以比较其生成的散列数。
想像一下，你需要比较下面的👇的两行字符串：

const A = "imagine that this is a string of 200 characters"
const B = "imagine that this is a string of 200 characterz"

想像一下他们有200个字符。比较它们是否相等，你可以使用一个暴力的方法比较每一个字符是否相等。就像下面这样：

const A = "imagine that this is a string of 200 characters"
const B = "imagine that this is a string of 200 characterz"
function equal(A, B) {
  let i;
  for(i = 0; i < A.length; i++){
    if (A[i] !== B[i]) {
      return false;
    }
  }
  return true;
}
console.log(equal(A,B));

对于大字符串的比较这不是最理想的，算法复杂度是O(min(A, B))。
当然我们可以添加条件比较A与B的大小，使它变成O(n)。就像这样：

function equal(A, B) {
  if (A.lenght !== B.length) return false;
  let i;
  for(i = 0; i < A.length; i++){
    if (A[i] !== B[i]) {
      return false;
    }
  }
  return true;
}

正如我所说的，最差也就是O(n)。试想一下比较一个大小不等的字符串呢？
字符串哈希是一个技术，它将我们的字符串转化为一个整数，作为散列数。因此，我们将比较两个哈希值hash(A) == hash(B)，算法复杂度是O(1)。这是比较两个字符串最好的选择。

字符串哈希的公式

p与m是素数，s[0], s[1], s[2]…是每一个字符的值。在这种情况下字符的值是字符编码。
p:它是一个素数，大致等于使用的不同字符数。比如，我们要计算的这个单词的哈希只包含英文字母表中的小写字母，31是一个很好的数字。然而，我们要是包含大写字母53是一个很好的选择。
m: 生成两个随机数，数字越大，出现相同的概率就越小。这个变量也应该是一个☝️素数。10 ^9 + 9是一个常见的选择。
例如：

p = 31
m = 1e9 + 9
word = 'apple'

我们想知道单词apple的哈希值，将数据带入到公式中，就像这样：

接着：

字符编码的值：

"a" = 97
"p" = 112
"p" = 112
"l" = 108
"e" = 101

替换公式：


最终：

可以得出单词apple的哈希值是96604250。
使用JavaScript实现：

function hash(word) {
    var p = 31;
    var m = 1e9 + 9;
    var hash_value = 0;
    for(var i = 0; i < word.length; i++) {
        var letter = word[i];
        var charCode = letter.charCodeAt();
        hash_value = hash_value + (charCode * Math.pow(p, i))
    }
    return hash_value % m;
}
console.log(hash("apple"));

原文：https://jorgechavez.dev/2020/11/12/string-hashing/