Java 中的 hashCode() 可以計算字串的雜湊值。日前有個朋友問:能不能在 JS 裡算出與 Java 完全相同結果的 hashCode?
按住 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,在散列分布與計算成本之間取得了不錯的平衡。