JavaScript中带有哈希表的“对象”有多高效？

Question

JavaScript中带有哈希表的“对象”有多高效？

3

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

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

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

查找速度会很快吗？我不需要超快速度，因为我不是亚马逊，但如果数据增长到比如2000个位置，是否会变慢？如果是，有什么好的替代方案吗？

- user949300

你测试过了吗？它应该非常快速。 - RobG

@RobG 在我理解的语言（Java）中编写一个好的基准测试已经很难了，更不用说在JavaScript这种相对陌生且可能存在许多基准测试“陷阱”的语言中了。因此，现在最容易的方法就是直接询问... - user949300

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jfriend00 · Accepted Answer

整个JavaScript引擎的性能很大程度上是基于对象属性查找的，因此我相信在基本的JS引擎中已经付出了相当大的努力来提高其性能。

但是，对于与性能有关的所有事情，您都应该自己进行测量。只需在jsperf中构建一个测试用例，然后将其与另一个版本进行比较，或者仅查看常规JS查找是否足够快速，这只需要几分钟时间。

在我的计算机上，这里有一个小型测试用例，显示每毫秒超过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(", "));