How efficient is a JavaScript "object" has a hash table?

Question

I am caching longitude and latitude (plus a bit more info) for possibly 1000s of locations, currently using a JavaScript hash, a {}. e.g.

var cache = {};
cache['Boston, MA'] = { id: someid, latlon: [lat, long] };
cache['Someotherplace, TX'] = { id: someotherid, latlon: [itslat, itslong]};

Everytime a new location comes up I do a geocode and add the results to the cache. I don't think Boston's latitude will change anytime soon...

Will lookups be reasonably fast? I don't need blazing fast, I'm not running Amazon, but as this data grows to, say 2000 locations, will it bog down? If so, what might be a good alternative?

Answer 1

Much of the performance of the entire javascript engine is based on property lookups on objects so I'm quite sure that significant effort has been paid to the performance of that in the basic JS engine.

But, as with all things related to performance you should measure yourself. It would only take a few minutes to build a test harness in jsperf and either compare it to an alternative or just see if regular JS lookup appears fast enough for you.

Here's a [little test harness][1] that shows more than 20,000 key lookups per ms on my computer. I would think that's fast enough for you.

function log(args) {
    var str = "";
    for (var i = 0; i < arguments.length; i++) {
        if (typeof arguments[i] === "object") {
            str += JSON.stringify(arguments[i]);
        } else {
            str += arguments[i];
        }
    }
    var div = document.createElement("div");
    div.innerHTML = str;
    document.body.appendChild(div);
}

function addCommas(str) {
    var amount = str + "";
    var parts = amount.split(".");
    amount = parts[0].split("").reverse();

    var output = "";
    for (var i = 0; i < amount.length; i++) {
        output = amount[i] + output;
        if ((i+1) % 3 == 0 && (amount.length-1) !== i) {
            output = ',' + output;
        }
    }
    if (parts.length > 1) {
        output += "." + parts[1];
    }
    return output;
}

function now() {
    return new Date().getTime();
}

// now fill the cache with a random set of keys
// the keys will var in length between minKeyLen and maxKeyLen
function createRandomKeys(num, minKeyLen, maxKeyLen, obj) {
    function rand(min, max) {
        return Math.floor(Math.random() * (max - min)) + min;
    }
    var chars = "abcdefghijlkmnopqrstuvwzyz";
    var len, key, numKeys = 0;
    while (numKeys < num) {
        // generate random key length
        len = rand(minKeyLen, maxKeyLen);
        key = "";
        // now select len random chars and combine into a string
        for (var j = 0; j < len; j++) {
            key += chars.charAt(rand(0, chars.length))
        }
        // put this key into our object, only count it if it's not already there
        if (!Object.prototype.hasOwnProperty.call(obj, key)) {
            ++numKeys;
            obj[key] = true;
        }
    }
}

var cache = {};
// put all the keys into our object
createRandomKeys(200000, 3, 15, cache);

// now get the list of keys, just so we know what to fetch in our test
var keys = Object.keys(cache);

// now time getting every key
var total = 0;
var start = now();
for (var i = 0; i < keys.length; i++) {
    if (cache[keys[i]]) {
        ++total;
    }
}
var end = now();
var elapsed = end - start;

log("Elapsed time = " + elapsed +  "ms for " + addCommas(keys.length) + " key lookups - found " + addCommas(total));
log(elapsed/keys.length + "ms per lookup");
log(addCommas((keys.length / elapsed).toFixed(2)) + " key lookups per ms");
// show some sample keys
log("<hr>Sample keys (first 100 keys):<br>");
log(keys.slice(0, 100).join(", "));