javascript (java-like) hash code implementation

2019-06-25 08:02发布

问题:

The following code is my attempt at a fairly generic javascript hash code implementation. I'm planning to use this code in conjunction with a hash table implementation (e.g. jshashtable) that utilizes hashCode() if its defined for keys. I have attempted to adhere closely to java's hash code implementations for numbers, strings, and arrays.

Questions:

  • Are there any issues with this implementation regarding correctness or performance?
  • Are there any pre-existing implementations for hash codes that do the same (or roughly the same) thing?
  • Aside from jshashtable, are there other hash table implementations that utilizes hashCode() and equals() in the same way that I should also consider?

NOTE: I'm aware that the code below could leverage other libs like underscore and jquery but I'd prefer not to have any 3rd party deps for my implementation. This is not say that I'm not interested in hash code libs that themselves may depend on jquery, underscore, etc.

/**
* 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);
}