DIV CSS 佈局教程網

用 JavaScript 實作與 Java 相容的 hashCode 演算法
編輯:JavaScript基礎知識     

Java 中的 hashCode() 可以計算字串的雜湊值。日前有個朋友問:能不能在 JS 裡算出與 Java 完全相同結果的 hashCode?

先看 Java 的原始實作

按住 Ctrl 點擊 hashCode 方法名追進原始碼,發現邏輯非常簡單:

public int hashCode() {
  int h = hash;
  if (h == 0) {
    int off = offset;
    char val[] = value;
    int len = count;

    for (int i = 0; i < len; i++) {
      h = 31 * h + val[off++];
    }
    hash = h;
  }
  return h;
}

核心就一句:h = 31 * h + 字元碼。移植到 JS 顯然不難:

<script type="text/javascript">
  function hashCode(str) {
    var h = 0, off = 0;
    var len = str.length;
    for (var i = 0; i < len; i++) {
      h = 31 * h + str.charCodeAt(off++);
    }
    return h;
  }

  alert(hashCode('沈陽'));   // 899755
</script>

執行結果 899755,與 Java 一致。看來搞定了。於是隨手又換一個字串測試:

「沈陽沈陽啊」在 Java 中的結果是 1062711668,而在 JS 中卻得到 26832515444。

問題所在:整數溢位

想了一下就明白了:Java 的 int 長度約在 21 億左右(上限 2147483647),超出會自動溢位回繞;而 JS 的數字是雙精度浮點,沒有這個限制。差異就出在這裡。於是改造一下:

<script>
  function hashCode(str) {
    var h = 0, off = 0;
    var len = str.length;
    for (var i = 0; i < len; i++) {
      h = 31 * h + str.charCodeAt(off++);
    }

    var t = -2147483648 * 2;
    while (h > 2147483647) {
      h += t;
    }
    return h;
  }

  alert(hashCode('沈陽沈陽啊'));   // 1062711668
</script>

再次測試,結果吻合,大功告成。

優化版本

上面那個寫法效率偏低:字串很長時,h 會變成極大的數值,while 迴圈要跑很多次甚至當掉。改為在迴圈內即時取模即可:

<script>
  function hashCode(str) {
    var h = 0;
    var len = str.length;
    var t = 2147483648;

    for (var i = 0; i < len; i++) {
      h = 31 * h + str.charCodeAt(i);
      if (h > 2147483647) h %= t;   // Java int 溢位則取模
    }

    return h;
  }

  alert(hashCode('C#同一時間N個線程在並發執行,其餘在隊列中如何實現'));   // 1107373715
</script>

更簡潔的位運算寫法

其實不必手動取模。JS 的位運算子會把運算元轉為 32 位元帶號整數,正好對應 Java 的 int 溢位行為:

function hashCode(str) {
  var h = 0;
  for (var i = 0; i < str.length; i++) {
    h = (31 * h + str.charCodeAt(i)) | 0;
  }
  return h;
}

或用 Math.imul 避免乘法精度損失,這在字元碼較大時更穩妥:

function hashCode(str) {
  var h = 0;
  for (var i = 0; i < str.length; i++) {
    h = (Math.imul(31, h) + str.charCodeAt(i)) | 0;
  }
  return h;
}

要注意的是,Java 的 hashCode() 以 UTF-16 的 char 為單位,JS 的 charCodeAt 同樣回傳 UTF-16 碼元,兩者因此能對齊;但若字串含 BMP 之外的字元(如 emoji),雙方都會以代理對的兩個碼元分別參與運算,結果仍然一致。這個 31 倍數的設計由來已久——它是奇數、質數,且 31 * h 可被編譯器優化為 (h << 5) - h,在散列分布與計算成本之間取得了不錯的平衡。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved