JavaScript“对象”具有哈希表的效率如何？

Question

我正在缓存可能有 1000 多个位置的经度和纬度（以及更多信息），目前使用的是 JavaScript 哈希值 {}。例如

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