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?

@RobG It's hard enough to write a good benchmark in a language I understand (Java), let alone in JavaScript, a language where I'm a relative newbie, that may have a lot of benchmark "gotchas". So for now it's much easier to just ask... — user949300
– user949300, Commented Mar 29, 2014 at 23:36

jfriend00 · Accepted Answer · 2018-03-02 07:02:54Z

6

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(", "));

edited Mar 2, 2018 at 7:02

answered Mar 29, 2014 at 21:13

jfriend00

711k104 gold badges1.1k silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user949300 Over a year ago

Thanks for the effort. The code is running in on a server in node.js, not sure if that has much of an effect on timings (vs. running in a browser), but this convinces me that the basic hash lookup is plenty fast enough for my purposes.

jfriend00 Over a year ago

Running in node.js, means that it is the Google V8 JS engine which is the fastest on this operation (much faster than what's in Firefox or IE for this operation) so you're good.

jfriend00 Over a year ago

Convert code to snippet that runs in place in the answer.

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related