Java 中有一個 hashCode 算法,可以計算字符串的 hash 值。某天朋友問我能不能在 JS 裡算出與 Java 一致的 hashCode。以前沒了解過它的算法,於是先在 Java 裡寫了段代碼測試,運行結果為 899755。
跟進 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;
}把它移植到 JS 裡:
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結果與 Java 一致。本以为搞定,於是隨便找了個更長的串「沈陽沈陽啊」測試:Java 中結果為 1062711668,JS 中卻成了 26832515444。
仔細一想,Java 的 int 長度大約 21 億,而 JS 沒有這個限制,問題就出在這裡。於是做了改造:
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('沈陽沈陽啊'));再次測試,結果一致,大功告成。
不過上面這種做法效率較低,內容很長時可能卡住,於是優化為在循環內取模:
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關鍵就在於模擬 Java int 的溢出行為——超過 2147483647 時取模,從而使 JS 的計算結果與 Java 完全對齊。