具有哈希表的JavaScript "object"效率如何？

Question

我缓存经度和纬度(加上更多的信息)可能1000个位置，目前使用JavaScript哈希，a{}。例如

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

每次出现新位置时，我都会进行地理编码并将结果添加到缓存中。我不认为波士顿的纬度会很快改变…

查找会相当快吗?我不需要超快的速度，我没有运行亚马逊，但是当数据增长到2000个地点时，它会陷入困境吗?如果是这样的话，有什么好的替代方案呢?

Answer 1

整个javascript引擎的大部分性能都是基于对象的属性查找，所以我很确定在基本JS引擎中已经付出了重大的努力来提高性能。

但是，与所有与性能相关的事情一样，你应该衡量自己。在jsperf中构建一个测试工具只需要几分钟的时间，并将其与替代方案进行比较，或者只是看看常规JS查找是否对您足够快。

这是一个[小测试工具][1]，显示在我的计算机上每毫秒有超过20,000个键查找。我想这对你来说已经够快了。

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