javascript - 那里有什么好的 JavaScript 哈希（代码/表）实现吗？

Question

是的，我知道您可以在 JavaScript 中使用常规对象作为关联数组，但我想使用更接近 java 的 Map 实现的东西（HashMap、LinkedHashMap 等）。可以将任何类型的数据用作密钥的东西。JavaScript 实现中有没有好的哈希（代码/表）？

Answer 1

在 javascript 中，对象实际上是一个哈希实现。Java HashMap 会有点假，所以我会挑战你重新考虑你的需求。

直接的答案是否定的，我不相信在 javascript 中有很好的 Java HashMap 实现。如果有，它一定是您可能想使用或不想使用的库的一部分，而且您当然不需要仅仅为了拥有一个小哈希表而包含一个库。

所以让我们继续写一个，只是为了检查这个问题。如果你喜欢，你可以使用它。我们将从编写一个构造函数开始，我们将捎带 Array，它是 Object，但有一些有用的方法可以避免这个例子变得过于乏味：

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 HashMap 之前重新检查问题。 Javascript 既不想也买不起。

记住原生替代品：

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

..相比之下如此快速和容易。

另一方面，我不相信这里有任何硬性的答案。这种实现确实可能是一个完全可以接受的解决方案。如果你觉得你可以使用它，我会说试一试。但是，如果我觉得我们有相当简单和更自然的方法可供我们使用，我永远不会使用它。我几乎可以肯定我们这样做了。

旁注： 效率与风格有关吗？请注意性能下降.. HashMap.put() 有一个大 O 盯着我们的脸...不太理想的性能可能不是这里的阻碍，你可能需要做一些非常雄心勃勃的东西或拥有大量数据，您甚至都不会注意到现代浏览器的性能提升。有趣的是，当您逆向工作时，操作的效率往往会降低，就好像有一个自然熵在起作用。Javascript 是一种高级语言，当我们遵守它的约定时应该提供有效的解决方案，就像 Java 中的 HashMap 将是一个更自然和高性能的选择一样。

Answer 2

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

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

Answer 3

请注意，使用“任何类型的对象”作为键的 java 集合并不完全正确。是的，您可以使用任何对象，但除非该对象具有良好的 hashcode() 和 equals() 实现，否则它将无法正常工作。基 Object 类具有这些的默认实现，但是要使自定义类（有效地）作为哈希表键工作，您需要覆盖它们。Javascript 没有等价物（据我所知）。

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

否则，您需要像发布的其他解决方案一样，到目前为止，这些解决方案的性能不像哈希表。他们都对列表进行 O(n) 搜索以尝试找到密钥，这几乎违背了哈希表的目的（哈希表通常是获取/放置的恒定时间）。

Answer 4

这是我刚刚放在一起的一个天真的实现 - 正如评论中提到的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"