有没有什么好的javascript散列(代码/表)实现?

在JavaScript中, 对象实际上是哈希实现 . Java哈希表会有点假的,所以我会 挑战你 重新思考你的需求。

这个 直截了当的回答是不 我不相信JavaScript中Java的哈希映射有很好的实现。如果有的话,它一定是一个图书馆的一部分,你可能想用,也可能不想用,当然 不需要包括库 只需要一个小哈希表。

所以我们继续写一篇,就为了 检查问题 . 如果你愿意,你可以用它。我们将从编写一个构造函数开始,我们将从对象数组开始,但有一些有用的方法可以防止这个例子变得过于单调:

function HashMap () {
    var obj = [];
    return obj;
}

var myHashMap = HashMap();

我们将直接从Java世界中添加一些方法,但是当我们去的时候转化成JavaScript…

function HashMap() {
    var obj = [];
    obj.size = function () {
        return this.length;
    };
    obj.isEmpty = function () {
        return this.length === 0;
    };
    obj.containsKey = function (key) {
        for (var i = 0; i < this.length; i++) {
            if (this[i].key === key) {
                return i;
            }
        }
        return -1;
    };
    obj.get = function (key) {
        var index = this.containsKey(key);
        if (index > -1) {
            return this[index].value;
        }
    };
    obj.put = function (key, value) {
        if (this.containsKey(key) !== -1) {
            return this.get(key);
        }
        this.push({'key': key, 'value': value});
    };
    obj.clear = function () {
        this = null;  // Just kidding...
    };
    return obj;
}

我们可以继续建设,但我认为这是错误的做法。最后,我们使用的是javascript在后台提供的内容,因为我们只是没有hashmap类型。在…的过程中 假装 ,它适合各种 额外工作 .

有点讽刺的是,让javascript成为如此有趣和多样化的语言的原因之一是它很容易处理这种 摔跤 . 我们可以按照字面意思做任何我们想做的事情,这里的快速例子如果不能说明语言的欺骗性力量,就什么也做不到。然而,考虑到这种力量,似乎 最好不要用它 .

我只是觉得javascript想要更轻一些。我个人的建议是,在尝试实现适当的Java HASMAP之前,请重新检查问题。 javascript既不需要也不提供 .

记住当地的选择 :

var map = [{}, 'string', 4, {}];

…相比之下,速度和容易。

另一方面,我不相信这里有任何困难和快速的答案。这个实现真的 可能是一个完全可以接受的解决方案 . 如果你觉得你能用的话,我会说 给它一个旋转 . 但如果我觉得我们 更简单更自然的方法 由我们决定……我几乎可以肯定我们是这样做的。

司扥噢特: 效率与风格有关吗?注意到 性能命中 …有一个大O正盯着我们的脸看hashmap.put()。不太理想的性能在这里可能不是一个展示的障碍,你可能需要做一些非常雄心勃勃的事情,或者在你注意到性能问题之前有大量的数据,一个现代的浏览器。有趣的是,当你处理谷物的时候,操作的效率会降低,就好像有一个自然熵在起作用。JavaScript是一种高级语言,当我们遵守它的约定时,应该提供有效的解决方案,就像Java中的HASMAP将是一个更自然和高性能的选择。

我已经发布了一个独立的javascript哈希表实现,它比这里列出的更进一步。

http://www.timdown.co.uk/jshashtable/

注意,使用“任何类型的对象”作为关键字的Java集合并不完全正确。是的,您可以使用任何对象,但除非该对象具有良好的hashcode()和equals()实现,否则它将无法正常工作。基本对象类有一个默认的实现,但是为了让自定义类作为哈希表键(有效地)工作,您需要重写它们。javascript没有等价物(我知道)。

要在javascript中创建一个哈希表,可以(有效地)使用任意对象作为键,您需要对所使用的对象强制执行类似的操作,至少如果您希望保持哈希表的性能提升。如果您可以强制执行返回字符串的“hashcode()”方法,那么您可以只使用引擎盖下的对象作为实际的哈希表。

否则,您就需要像其他发布的解决方案那样,而到目前为止,这些解决方案的性能并不像哈希表那样。它们都在列表中进行O(N)搜索,试图找到键,这几乎破坏了哈希表的目的(哈希表通常是获取/输出的恒定时间)。

这是我刚刚总结的一个幼稚的实现——正如Keparo在评论中提到的,其中一个大问题是平等检查:

var ObjectMap = function()
{
    this._keys = [];
    this._values = [];
};

ObjectMap.prototype.clear = function()
{
    this._keys = [];
    this._values = [];
};

ObjectMap.prototype.get = function(key)
{
    var index = this._indexOf(key, this._keys);
    if (index != -1)
    {
        return this._values[index];
    }
    return undefined;
};

ObjectMap.prototype.hasKey = function(key)
{
    return (this._indexOf(key, this._keys) != -1);
};

ObjectMap.prototype.hasValue = function(value)
{
    return (this._indexOf(value, this._values) != -1);
};

ObjectMap.prototype.put = function(key, value)
{
    var index = this._indexOf(key, this._keys);
    if (index == -1)
    {
        index = this._keys.length;
    }

    this._keys[index] = key;
    this._values[index] = value;
};

ObjectMap.prototype.remove = function(key)
{
    var index = this._indexOf(key, this._keys);
    if (index != -1)
    {
        this._keys.splice(index, 1);
        this._values.splice(index, 1);
    }
};

ObjectMap.prototype.size = function()
{
    return this._keys.length;
};

ObjectMap.prototype._indexOf = function(item, list)
{
    for (var i = 0, l = list.length; i < l; i++)
    {
        if (this._equals(list[i], item))
        {
            return i;
        }
    }
    return -1;
};

ObjectMap.prototype._equals = function(a, b)
{
    if (a === b)
    {
        return true;
    }

    // Custom objects can implement an equals method
    if (typeof a.equals == "function" &&
        typeof b.equals == "function")
    {
        return a.equals(b);
    }

    // Arrays are equal if they're the same length and their contents are equal
    if (a instanceof Array && b instanceof Array)
    {
        if (a.length != b.length)
        {
            return false;
        }

        for (var i = 0, l = a.length; i < l; i++)
        {
            if (!this._equals(a[i], b[i]))
            {
                return false;
            }
        }

        return true;
    }

    // Checking object properties - objects are equal if they have all the same
    // properties and they're all equal.
    var seenProperties = {};
    for (var prop in a)
    {
        if (a.hasOwnProperty(prop))
        {
            if (!b.hasOwnProperty(prop))
            {
                return false;
            }

            if (!this._equals(a[prop], b[prop]))
            {
                return false;
            }

            seenProperties[prop] = true;
        }
    }

    for (var prop in b)
    {
        if (!(prop in seenProperties) && b.hasOwnProperty(prop))
        {
            if (!a.hasOwnProperty(prop))
            {
                return false;
            }

            if (!this._equals(b[prop], a[prop]))
            {
                return false;
            }
        }
    }

    return true;
};

示例用法:

>>> var map = new ObjectMap();
>>> var o = {a: 1, b: [1,2], c: true};
>>> map.put(o, "buns");
>>> map.get(o)
"buns"
>>> map.get({a: 1, b: [1,2], c: true});
"buns"
>>> map.get({a: 1, b: [1,2], c: true, d:"hi"});
>>> var a = [1,2,3];
>>> map.put(a, "cheese");
>>> map.get(a);
"cheese"
>>> map.get([1,2,3]);
"cheese"
>>> map.get([1,2,3,4]);
>>> var d = new Date();
>>> map.put(d, "toast");
>>> map.get(d);
"toast"
>>> map.get(new Date(d.valueOf()));
"toast"

这绝不是一个完整的实现,只是一个用于实现此类对象的方法的指针。例如,查看我给出的内容,您还需要在对象属性检查之前添加构造函数属性检查,因为这目前有效:

>>> function TestObject(a) { this.a = a; };
>>> var t = new TestObject("sandwich");
>>> map.put(t, "butter");
>>> map.get({a: "sandwich"})
"butter"