Skip to content

Instantly share code, notes, and snippets.

@stamat

stamat/HashCache.js

Last active Feb 19, 2016
Embed
What would you like to do?
A hash table value value storage for quick seek in large lists of big objects/arrays/strings. It uses CRC32 algorithm to convert supplied values into integer hashes and produce more elegant solution escaping data redundancy and heavy memory loads but also leaning on native hash map implementation for seek speed and optimization.
/**
* A hash table value value storage for quick seek in large lists of big objects/arrays/strings.
* It uses CRC32 algorithm to convert supplied values into integer hashes and produce more elegant solution escaping data redundancy and heavy memory loads but also leaning on native hash map implementation for seek speed and optimization.
*
* @author Nikola Stamatovic Stamat < stamat@ivartech.com >
* @copyright ivartech < http://ivartech.com >
* @version 1.0
* @date 2013-07-02
* @namespace ivar.data
*/
/**
* @class
* @param {array} a An array of values to store on init
*/
var HashCache = function(a) {
/**
* Keeps values in arrays labeled under typewise crc32 hashes
*
* @this HashCache
* @protected
*/
var storage = {};
/**
* Produces an integer hash of a given value
* If the object is passed, before JSON stringification the properties are ordered. Note that because crc32 hashes strings, then boolean true would be the same as string 'true' or a sting '123' would be the same as integer 123, etc... We could add some modifier to solve this but a chance of using this with a set of values different by type is low in common use.
*
* @this HashCache
* @protected
* @param {any} value Any value to be hashed
* @return {integer} Integer hash
*
* @see orderedStringify
* @see arrayStringify
* @see whatis
* @see types
*/
var hashFn = function(value) {
var type = types[whatis(value)];
if (type === 2) {
value = orderedStringify(value);
} else if(type === 3) {
value = arrayStringify();
} else {
value = value.toString();
}
return crc32(value);
};
/**
* Checks if the value is stored under the selected hash key.
* Under the same hash can be stored one or more values, this happens due to hash collisions and entries other then first element of the array are called overflow entries.
*
* @this HashCache
* @protected
*
* @param {integer} hash Hash of the value
* @param {any} value Submited value
* @return {boolean} Returns if the value is listed under its hash in HashCache instance
*
* @see HashCache.storage
* @see equal
*/
var hashHoldsValue = function(hash, value) {
var bucket = storage[hash]
if (bucket && bucket.length > 0) {
for (var i = 0; i < bucket.length; i++) {
if(equal(bucket[i], value))
return true;
}
}
return false
};
/**
* Hashes the value and stores it in the hash table where the generated hash is a key
*
* @this {HashCache}
* @public
* @param {any} value Any value to be stored
*
* @see HashCache.hashFn
* @see HashCache.hashHoldsValue
* @see HashCache.storage
*/
this.put = function(value) {
var hash = hashFn(value);
if(!hashHoldsValue(hash, value)) {
if (storage.hasOwnProperty(hash)) {
storage[hash].push(value);
} else {
storage[hash] = [value];
}
}
}
/**
* Checks if the value is listed in HashCache instance
*
* @this HashCache
* @public
* @param {any} value Any value to be checked
* @return {boolean} If the value is listed
*
* @see HashCache.hashFn
* @see HashCache.hashHoldsValue
*/
this.exists = function(value) {
var hash = hashFn(value);
return hashHoldsValue(hash, value);
}
/**
* Finds the value listed and removes it from the HashCache instance
*
* @this HashCache
* @public
* @param {any} value Any value to be removed
* @return {boolean} If the value existed and was removed
*
* @see HashCache.hashFn
* @see HashCache.storage
* @see equal
*/
this.remove = function(value) {
var hash = hashFn(value);
var bucket = storage[hash];
var res = false;
if(bucket && bucket.length > 0) {
for (var i = 0; i < bucket.length; i++) {
if(equal(bucket[i], value)) {
storage[hash].splice(i, 1);
res = true;
}
}
//Clean up
if(bucket.length === 0) {
delete storage[hash];
}
}
return res;
}
//INIT
if (a !== undefined && whatis(a) === 'array') {
for (var i = 0; i < a.length; i++) {
this.put(a[i]);
}
}
};
var whatis = function(val) {
if (val === undefined)
return 'undefined';
if (val === null)
return 'null';
var type = typeof val;
if (type === 'object')
type = getClass(val).toLowerCase();
if (type === 'number') {
if (val.toString().indexOf('.') > 0)
return 'float';
else
return 'integer';
}
return type;
};
var types = {
'integer': 0,
'float': 0,
'string': 1,
'array': 2,
'object': 3,
'function': 4,
'regexp': 5,
'date': 6,
'null': 7,
'undefined': 8,
'boolean': 9
};
var orderedStringify = function(o, fn) {
var props = [];
var res = '{';
for(var i in o) {
props.push(i);
}
props = props.sort(fn);
for(var i = 0; i < props.length; i++) {
var val = o[props[i]];
var type = types[whatis(val)];
if(type === 3) {
val = orderedStringify(val, fn);
} else if(type === 2) {
val = arrayStringify(val, fn);
} else if(type === 1) {
val = '"'+val+'"';
}
if(type !== 4)
res += '"'+props[i]+'":'+ val+',';
}
return res.substring(res, res.lastIndexOf(','))+'}';
};
//orderedStringify for array containing objects
var arrayStringify = function(a, fn) {
var res = '[';
for(var i = 0; i < a.length; i++) {
var val = a[i];
var type = types[whatis(val)];
if(type === 3) {
val = orderedStringify(val, fn);
} else if(type === 2) {
val = arrayStringify(val, fn);
} else if(type === 1) {
val = '"'+val+'"';
}
if(type !== 4)
res += ''+ val+',';
}
return res.substring(res, res.lastIndexOf(','))+']';
};
/**
* Compares two objects
*
* @param {object} a Any object with properties
* @param {object} b Any object with properties
* @return {boolean} True if equal
*/
var compareObjects = function(a, b) {
if (a === b)
return true;
for(var i in a) {
if(b.hasOwnProperty(i)) {
if(!equal(a[i],b[i])) return false;
} else {
return false;
}
}
for(var i in b) {
if(!a.hasOwnProperty(i)) {
return false;
}
}
return true;
};
var compareArrays = function(a, b) {
if (a === b)
return true;
if (a.length !== b.length)
return false;
for(var i = 0; i < a.length; i++){
if(!equal(a[i], b[i])) return false;
};
return true;
};
var _equal = {};
_equal.array = compareArrays;
_equal.object = compareObjects;
_equal.date = function(a, b) {
return a.getTime() === b.getTime();
};
_equal.regexp = function(a, b) {
return a.toString() === b.toString();
};
_equal['function'] = _equal.regexp;
/*
* Are two values equal, deep compare for objects and arrays.
* @param {any} a
* @param {any} b
* @return {boolean} Are equal?
*/
var equal = function(a, b) {
if (a !== b) {
var atype = whatis(a), btype = whatis(b);
if (atype === btype)
return _equal.hasOwnProperty(atype) ? _equal[atype](a, b) : a==b;
return false;
}
return true;
};
//Thanks to perfectionkills.com <http://perfectionkills.com/instanceof-considered-harmful-or-how-to-write-a-robust-isarray/>
var getClass = function(val) {
return Object.prototype.toString.call(val)
.match(/^\[object\s(.*)\]$/)[1];
};
/*
===============================================================================
Crc32 is a JavaScript function for computing the CRC32 of a string
...............................................................................
Version: 1.2 - 2006/11 - http://noteslog.com/category/javascript/
-------------------------------------------------------------------------------
Copyright (c) 2006 Andrea Ercolino
http://www.opensource.org/licenses/mit-license.php
===============================================================================
*/
var crc32_table = [0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D]
/* Number */
var crc32 = function( /* String */ str, /* Number */ crc ) {
if( crc == window.undefined ) crc = 0;
var n = 0; //a number between 0 and 255
var x = 0; //an hex number
crc = crc ^ (-1);
for( var i = 0, iTop = str.length; i < iTop; i++ ) {
n = ( crc ^ str.charCodeAt( i ) ) & 0xFF;
crc = ( crc >>> 8 ) ^ crc32_table[n];
}
return crc ^ (-1);
};
@twobob

This comment has been minimized.

Copy link

@twobob twobob commented Feb 18, 2016

I'm sure the examples on your page fail with an "a not defined" when used with this... maybe the html got mangled? unsure but when we tested the copy/paste it bombed that way.

EDIT: okay so it was

var hc = new HashCache([{a:3, b:2, c:5}, {a:15, b:2, c:'foo'}]); //init
hc.put({a:1, b:1});
hc.put({b:1, a:1});

the second and third obvioulsy bomb. maybe just make https://stamat.wordpress.com/2013/07/03/javascript-quickly-find-very-large-objects-in-a-large-array/ a bit more obvious what you are doing.

However - great piece of work, once we got used to it.
N.B. DO wrap your stuff in { [ ] } or expect the above error.
However you can also just put("value","value","value") as well :)
Thanks for the thing

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment