Murmur3 Hash Table in JavaScript

superHashTable.js

/**
 * MURMUR 3 HASH TABLE WITH OBJECT HASHING
 *
 * A hash table with `insert()`, `retrieve()`, and `remove()` methods.
 * It handles hashing collisions correctly. And doubles the storage
 * limit as soon as the total number of items stored is greater than
 * 3/4th of the number of slots in the storage array.
 * It resizes by half whenever utilization drops below 1/4.
 * It also caches insertions at runtime for even faster retrieval.
 */

//import murmur3 super hash algorithm
var murmur = require('./murmurHash3');

var makeHashTable = function() {
    //global private varibables
    var _size = 0;
    var _storageLimit = 8;
    var _storage = [];
    var _cache = {};

    //hash table object;
    var hashTable = {

        //hash table methods
        insert: function(key, value) {
            var index = _hashify(key, _storageLimit);
            key = _keyHasher(key);
            var bucket = _storage[index];
            var tuple = [key, value];
            var overwrite = false;
            // cache new insertions
            if (!_cache[key]) _cache[key] = value;
            if (!bucket) _storage[index] = [tuple];
            //invoke collison resolution
            else overwrite = _collision(tuple, bucket, key, value);
            _size += overwrite ? 0 : 1;
            //check to see if the hash table need to be resized
            if (_size >= _storageLimit * 0.75) this.resize(2);
        },

        retrieve: function(key) {
            // check _cache first 
            key = _keyHasher(key);
            if (_cache[key]) return _cache[key];
            var index = _hashify(key, _storageLimit);
            var bucket = _storage[index];
            if (!bucket) return false;
            var found = bucket.filter(function(tuple) {
                if (tuple[0] === key) return true;
            })
            return found.length ? found[0][1] : false;
        },

        remove: function(key) {
            var index = _hashify(key, _storageLimit);
            var bucket = _storage[index];
            var removed = false;
            key = _keyHasher(key);
            if (_cache[key]) delete _cache[key] // remove from cache
            if (!bucket) return null;
            bucket.forEach(function(tuple, index) {
                if (tuple[0] === key) {
                    removed = tuple[1];
                    bucket.splice(index, 1);
                    _size--;
                }
            });
            if (_size <= _storageLimit * 0.25) this.resize(0.5);
            return removed;
        },

        resize: function(factor) {
            var clonedStorage = JSON.parse(JSON.stringify(_storage)); //deep clone of storage
            _storageLimit *= factor; //increase or decrease limit
            _storage = []; //clear storage
            _size = 0; //reset size
            clonedStorage.forEach(function(bucket) {
                if (bucket) {
                    bucket.forEach(function(tuple) {
                        this.insert(tuple[1], tuple[1]);
                    }.bind(this));
                }
            }.bind(this));
            clonedStorage = []; //clear clone after resizing;
        },

        peek: function() {
            return {
                storage: _storage,
                size: _size,
                limit: _storageLimit,
                cache: _cache
            };
        }

    };

    //global private functions
    function _hashify(key, max) {

        /* https://github.com/karanlyons/murmurHash3.js/tree/master
           using the Murmur3 Hashing Algorithm;
           Returns a 32bit hash as a unsigned int
           with the max used as a seed 
        */

        return (key instanceof Object) ?
            murmur.x86.hash32(JSON.stringify(key), max) % max :
            murmur.x86.hash32(key, max) % max;

        /* or you can use this much simpler hash function

        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash = (hash << 5) + hash + key.charCodeAt(i);
            hash = hash & hash; // Convert to 32bit integer
            hash = Math.abs(hash);
        } */
    }

    function _keyHasher(key) {
        return murmur.x86.hash128(JSON.stringify(key), 25);
    }

    //resolve collsions upon insertion
    function _collision(tuple, bucket, key, value) {
        var overwrite = false;
        for (var i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value;
                overwrite = true;
                break;
            }
        }
        if (!overwrite) bucket.push(tuple);
        return overwrite;
    }

    return hashTable;
};


//TESTS

var dictionary = makeHashTable();

// for (var i = 0; i < 100; i++) {
//    dictionary.insert(Math.random().toString(36).slice(9), Math.random().toString(36).slice(2));
// }

var user1 = {
    username: "johncage",
    firstName: "John",
    lastName: "Doe",
    age: 50,
    eyeColor: "blue"
};
var user2 = {
    username: "achawkins",
    firstName: "Alex",
    lastName: "Doe",
    age: 56,
    eyeColor: "blue"
};
var user3 = {
    username: "walkerdoe",
    firstName: "Walker",
    lastName: "Doe",
    age: 27,
    eyeColor: "blue"
};
var user4 = {
    username: "slick",
    firstName: "Slick",
    lastName: "Doe",
    age: 29,
    eyeColor: "blue"
};
var user5 = {
    username: "rickey",
    firstName: "Rick",
    lastName: "Doe",
    age: 100,
    eyeColor: "blue"
};
var user6 = {
    username: "hansgruber",
    firstName: "Hans",
    lastName: "Gruber",
    age: 19,
    eyeColor: "blue"
};
var user7 = {
    username: "bifftannin",
    firstName: "Biff",
    lastName: "Tanin",
    age: 12,
    eyeColor: "blue"
};
var user8 = {
    username: "bojackson",
    firstName: "Bo",
    lastName: "Knows",
    age: 40,
    eyeColor: "green"
};

dictionary.insert(user1, user1);
dictionary.insert(user2, user2);
dictionary.insert(user3, user3);
dictionary.insert(user4, user4);
dictionary.insert(user5, user5);
dictionary.insert(user6, user6);
dictionary.insert(user7, user7);
dictionary.insert(user8, user8);

console.log('AFTER INSERTIONS', dictionary.peek().cache);
//dictionary.insert('achawkins', '20nfrqcmbfadzpvi');
console.log('FIND PERSON: ', dictionary.retrieve(user3).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user1).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user2).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user4).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user5).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user6).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user7).firstName);
console.log('FIND PERSON: ', dictionary.retrieve(user8).firstName);
// FIND PERSON:  Walker
// FIND PERSON:  John
// FIND PERSON:  Alex
// FIND PERSON:  Slick
// FIND PERSON:  Rick
// FIND PERSON:  Hans
// FIND PERSON:  Biff
// FIND PERSON:  Bo

console.log('REMOVE PERSON: ', dictionary.remove(user8));

// REMOVE PERSON:  { username: 'bojackson',
//   firstName: 'Bo',
//   lastName: 'Knows',
//   age: 40,
//   eyeColor: 'green' }

console.log('FIND PERSON: ', dictionary.retrieve(user8).firstName);
console.log(dictionary.peek().storage);
// [ ,
//   [ [ '319902ad2f70896aac37ff66a81c2301', [Object] ] ],
//   [ [ '61b5b8e78cc3ff01ee3af9317075b2ff', [Object] ] ],
//   ,
//   [ [ 'b8ae22811ba5cffc418b0d61de3c0636', [Object] ] ],
//   ,
//   [ [ '0d9ff57098a26848baac24c0e81cb2c1', [Object] ] ],
//   [ [ 'd79a5863cef57650fea8caa4d0bac87a', [Object] ] ],
//   ,
//   ,
//   ,
//   ,
//   [ [ 'c3e11fc88baaddec0a1c95287b6ea1e1', [Object] ],
//     [ 'ddc4aa2b7c47443d68c25493c27f1c81', [Object] ] ] ]
// [ ,
//   [ [ '319902ad2f70896aac37ff66a81c2301', [Object] ] ],
//   [ [ '61b5b8e78cc3ff01ee3af9317075b2ff', [Object] ] ],
//   ,
//   [ [ 'b8ae22811ba5cffc418b0d61de3c0636', [Object] ],
//     [ 'e8872d388f9c82955674b8e7c45588e5', [Object] ] ],
//   ,
//   [ [ '0d9ff57098a26848baac24c0e81cb2c1', [Object] ] ],
//   [ [ 'd79a5863cef57650fea8caa4d0bac87a', [Object] ] ],
//   ,
//   ,
//   ,
//   ,
//   [ [ 'c3e11fc88baaddec0a1c95287b6ea1e1', [Object] ],
//     [ 'ddc4aa2b7c47443d68c25493c27f1c81', [Object] ] ] ]

dictionary.insert(user8, user8);
console.log(dictionary.peek().cache);
console.log('FIND PERSON: ', dictionary.retrieve(user8).firstName);

//CACHE LOOKS LIKE THIS
// { '4af32d57bb8c5aa270ce10593ae2ffad':
//    { username: 'johncage',
//      firstName: 'John',
//      lastName: 'Doe',
//      age: 50,
//      eyeColor: 'blue' },
//   bfd1c9d0c77e2953aad7ae0692beccb8:
//    { username: 'achawkins',
//      firstName: 'Alex',
//      lastName: 'Doe',
//      age: 56,
//      eyeColor: 'blue' },
//   '6734e9cbf560fb09b48c0e1407acf0e7':
//    { username: 'walkerdoe',
//      firstName: 'Walker',
//      lastName: 'Doe',
//      age: 27,
//      eyeColor: 'blue' },
//   '96bb4c07eebdfa01ce2dbff6b0ad8618':
//    { username: 'slick',
//      firstName: 'Slick',
//      lastName: 'Doe',
//      age: 29,
//      eyeColor: 'blue' },
//   d10b08c1897358487c8324ed49075576:
//    { username: 'rickey',
//      firstName: 'Rick',
//      lastName: 'Doe',
//      age: 100,
//      eyeColor: 'blue' },
//   '7e4546ebf65babfe168c5c035defa4d2':
//    { username: 'hansgruber',
//      firstName: 'Hans',
//      lastName: 'Gruber',
//      age: 19,
//      eyeColor: 'blue' },
//   c3e11fc88baaddec0a1c95287b6ea1e1:
//    { username: 'slick',
//      firstName: 'Slick',
//      lastName: 'Doe',
//      age: 29,
//      eyeColor: 'blue' },
//   b8ae22811ba5cffc418b0d61de3c0636:
//    { username: 'johncage',
//      firstName: 'John',
//      lastName: 'Doe',
//      age: 50,
//      eyeColor: 'blue' },
//   '0d9ff57098a26848baac24c0e81cb2c1':
//    { username: 'achawkins',
//      firstName: 'Alex',
//      lastName: 'Doe',
//      age: 56,
//      eyeColor: 'blue' },
//   '319902ad2f70896aac37ff66a81c2301':
//    { username: 'hansgruber',
//      firstName: 'Hans',
//      lastName: 'Gruber',
//      age: 19,
//      eyeColor: 'blue' },
//   d79a5863cef57650fea8caa4d0bac87a:
//    { username: 'walkerdoe',
//      firstName: 'Walker',
//      lastName: 'Doe',
//      age: 27,
//      eyeColor: 'blue' },
//   '61b5b8e78cc3ff01ee3af9317075b2ff':
//    { username: 'rickey',
//      firstName: 'Rick',
//      lastName: 'Doe',
//      age: 100,
//      eyeColor: 'blue' },
//   ddc4aa2b7c47443d68c25493c27f1c81:
//    { username: 'bifftannin',
//      firstName: 'Biff',
//      lastName: 'Tanin',
//      age: 12,
//      eyeColor: 'blue' },
//   e8872d388f9c82955674b8e7c45588e5:
//    { username: 'bojackson',
//      firstName: 'Bo',
//      lastName: 'Knows',
//      age: 40,
//      eyeColor: 'green' } }

// dictionary.insert('lexluther', Math.random().toString(36).slice(2));
// dictionary.insert('haywoodjablomi', Math.random().toString(36).slice(2));
// dictionary.insert('kevinkiller', Math.random().toString(36).slice(2));
// dictionary.insert('achawkins', 'gabagoosegabagoose');
// console.log(dictionary.peek());
// console.log(dictionary.peek().storage);
// console.log('RETRIEVE PASSWORD: ', dictionary.retrieve('lexluther'));
// //RETRIEVE PASSWORD:  jmoh113l127f1or
// console.log('REMOVED USER: ', dictionary.remove('haywoodjablomi'));
// //REMOVED USER:  [ 'haywoodjablomi', '6adlanx1zfflxr' ]
// console.log(dictionary.peek());

// //TEST RESIZING
// console.log('REMOVED USER: ', dictionary.remove('kevinkiller'));
// console.log('REMOVED USER: ', dictionary.remove('lexluther'));
// console.log('REMOVED USER: ', dictionary.remove('achawkins'));

// console.log('AFTER REMOVAL: ', dictionary.peek());
// dictionary.insert('dawsonwillis', '20nfrqcmbfadzpvi');
// dictionary.insert('skeelow', Math.random().toString(36).slice(2));
// dictionary.insert('crackerjohn', Math.random().toString(36).slice(2));
// dictionary.insert('hansgruber', Math.random().toString(36).slice(2));
// dictionary.insert('lexingtonsteel', '23234kjqwhq2l4q234i');
// //TEST OVERWRITING
// dictionary.insert('dawsonwillis', '20nfrqcmbfadzpvi');
// dictionary.insert('skeelow', Math.random().toString(36).slice(2));
// dictionary.insert('crackerjohn', Math.random().toString(36).slice(2));
// dictionary.insert('hansgruber', Math.random().toString(36).slice(2));
// dictionary.insert('lexingtonsteel', '23234kjqwhq2l4q234i');
// console.log('AFTER INSERTION: ', dictionary.peek());

// console.log('RETRIEVE PASSWORD: ', dictionary.retrieve('lexluther'));
// console.log('RETRIEVE PASSWORD: ', dictionary.retrieve('crackerjohn'));
// console.log('RETRIEVE PASSWORD: ', dictionary.retrieve('skeelow')); //RETRIEVE PASSWORD:  t4gtord34q9kvs4i
//console.log('RETRIEVE PASSWORD: ', dictionary.retrieve('achawkins')); //RETRIEVE PASSWORD:  gabagoosegabagoose
// console.log('RETRIEVE PASSWORD: ', dictionary.retrieve('kevinkiller')); //RETRIEVE PASSWORD:  01r8of5js8twqaor
// console.log('REMOVED USER: ', dictionary.remove('kevinkiller'));
// console.log(dictionary.peek().storage);