以下代码是我对相当通用的 javascript 哈希代码实现的尝试。我计划将此代码与哈希表实现(例如 jshashtable)结合使用,该哈希表实现使用 hashCode()(如果为键定义)。我尝试严格遵守 java 的数字、字符串和数组的哈希码实现。
问题:
- 此实现在正确性方面是否存在任何问题
还是性能?
- 是否有任何预先存在的哈希实现
执行相同(或大致相同)操作的代码?
- 除了
jshashtable,还有其他利用的哈希表实现吗
hashCode() 和 equals() 以同样的方式我也应该考虑?
注意:我知道下面的代码可以利用其他库,例如下划线和 jquery,但我不希望在我的实现中使用任何第三方依赖。这并不是说我对哈希码库不感兴趣,它们本身可能依赖于 jquery、下划线等。
/**
* Computes a hash code for an object based on a given subset of its fields
* @param obj any type
* @param keys an array of strings representing some subset of the keys in obj or undefined
* @returns {Number} a java-like hash code for obj based on the hash codes of a subset of its fields
* specified in keys.
*/
function hashCode(obj, keys) {
if (!isDefined(keys)) return typeHashCode(obj);
var result = 1;
for (var k = 0; k < keys.length; k++) {
var key = keys[k];
if (isDefined(obj[key]))
result = multiplyBy31AndAdd(result, typeHashCode(obj[key]));
}
return result;
}
/**
* @param obj
* @returns {Number}
*/
function typeHashCode(obj) {
var result = 1;
if (isDefined(obj)) {
if (typeof obj === 'string')
result = multiplyBy31AndAdd(result, stringHashCode(obj));
else if (typeof obj === 'number' && isFinite(obj))
result = multiplyBy31AndAdd(result, numberHashCode(obj));
else if (typeof obj === 'object') {
if (nonEmptyObject(obj)) {
if (isDefined(obj[hashCode]))
result = multiplyBy31AndAdd(result, obj.hashCode());
else {
if (Array.isArray(obj))
result = multiplyBy31AndAdd(result, arrayHashCode(obj));
else {
//This is what jshashtable does. If there were an easy and agreed upon way
//of uniquely identifying objects in javascript, a better approach
//may be to use the object's id
result = multiplyBy31AndAdd(result, stringHashCode(obj.toString()));
}
}
}
}
}
return result;
}
/**
* Generates a hash code for a 64 bit floating point number, similar to java's hash
* code implementation. This does not handle NaN and Inf the same way as java.
* More info can be found at [1]
* [1] http://stackoverflow.com/questions/2003493/javascript-float-from-to-bits
* @param num a finite number as defined by isFinite()
* @returns {Number}
*/
function numberHashCode(num) {
var buf = new ArrayBuffer(8);
(new Float64Array(buf))[0] = num;
return (new Uint32Array(buf))[0] ^ (new Uint32Array(buf))[1];
}
/**
* Generates a hash code for a string, similar to java's hash code
* implementation. More info can be found at [1]
* [1] http://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript-jquery
* @returns {Number}
*/
function stringHashCode(str) {
var hash = 0;
if (str.length === 0) return hash;
for (var i = 0; i < str.length; i++) {
var character = str.charCodeAt(i);
hash = multiplyBy31AndAdd(hash, character);
}
return hash;
}
/**
* @param array
* @returns {Number} hash code for the array
*/
function arrayHashCode(array) {
var result = 1;
for (var i = 0; i < array.length; i++) {
result = multiplyBy31AndAdd(result, typeHashCode(obj));
}
return result;
}
/**
* Code taken from:
* http://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript-jquery
* @param currentValue a number
* @param toAdd a number
* @returns {Number} the 32 bit integer representation of 31 * currentValue + toAdd
*/
function multiplyBy31AndAdd(currentValue, toAdd) {
var rv = ((currentValue<<5)-currentValue)+toAdd;
return rv & rv; //Convert to 32 bit integer
}
function isDefined(obj) {
return !(obj === undefined || obj === null);
}
/**
* Taken from http://stackoverflow.com/questions/4994201/is-object-empty
* @param obj an object
* @returns {Boolean} obj is {}
*/
function nonEmptyObject(obj) {
return !(Object.keys(obj).length === 0);
}
None
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)