Gibt es eine gute JavaScript Hash (Code/Tabelle) Implementierung da draußen?

Question

Ja, ich weiß, Sie könnten reguläre Objekte als assoziative Arrays in JavaScript verwenden, aber ich möchte etwas näher an Java's Map-Implementierung (HashMap, LinkedHashMap etc.) verwenden. Etwas, das jede Art von Daten als Schlüssel verwendet haben könnte. Gibt es eine gute Hash (Code/Tabelle) in JavaScript-Implementierung da draußen?

Answer 1

In Javascript, Objekte sind buchstäblich eine Hash-Implementierung . Eine Java-HashMap wird ein wenig unübersichtlich sein, daher würde ich Sie herausfordern Ihre Bedürfnisse zu überdenken.

El die direkte Antwort ist nein Ich glaube nicht, dass es eine große Implementierung von Java's HashMap in Javascript ist. Wenn es ist, ist es verpflichtet, Teil einer Bibliothek, die Sie können oder nicht verwenden möchten, und Sie sicherlich sein keine Bibliothek enthalten müssen nur um eine kleine Hashtabelle zu haben.

Schreiben wir also einen, nur um das Problem untersuchen . Sie können es verwenden, wenn Sie möchten. Wir beginnen einfach damit, einen Konstruktor zu schreiben, und wir nutzen Array, das zwar Object ist, aber einige nützliche Methoden hat, damit dieses Beispiel nicht zu langweilig wird:

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

var myHashMap = HashMap();

Wir fügen einige Methoden direkt aus der Java-Welt hinzu, übersetzen sie aber nach und nach in 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;
}

Wir könnten es weiter ausbauen, aber ich halte das für den falschen Ansatz. Am Ende des Tages, wir am Ende mit, was Javascript hinter den Kulissen bietet, weil wir einfach nicht die HashMap Typ haben. In dem Prozess der so tun, als ob eignet sie sich für alle Arten von Mehrarbeit .

Es ist ein bisschen ironisch, dass eines der Dinge, die Javascript zu einer so interessanten und vielfältigen Sprache machen, die Leichtigkeit ist, mit der es diese Art von Wrestling . Wir können buchstäblich alles tun, was wir wollen, und das kurze Beispiel hier bringt nichts, wenn es nicht die trügerische Macht der Sprache verdeutlicht. Doch angesichts dieser Macht, scheint es am besten nicht verwenden .

Ich glaube einfach, dass Javascript leichter sein will. Meine persönliche Empfehlung ist, dass Sie das Problem erneut zu untersuchen, bevor Sie versuchen, eine ordnungsgemäße Java HashMap zu implementieren. Javascript will und kann man sich nicht leisten .

Denken Sie an die einheimische Alternative :

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

so schnell und einfach im Vergleich.

Andererseits glaube ich nicht, dass es hier eine eindeutige Antwort gibt. Diese Implementierung ist wirklich kann eine durchaus akzeptable Lösung sein . Wenn Sie meinen, dass Sie es gebrauchen können, würde ich sagen probieren Sie es aus . Aber ich würde es nie benutzen, wenn ich das Gefühl hätte, dass wir vernünftigerweise einfachere und natürlichere Mittel und ich bin mir fast sicher, dass wir sie haben.

Sidenote: Hängt Effizienz mit Stil zusammen? Beachten Sie die Performance-Hit ... gibt es ein großes O, das uns bei HashMap.put() ins Gesicht starrt... Die weniger als optimale Leistung ist hier wahrscheinlich kein Hindernis, und man müsste schon etwas sehr Ehrgeiziges machen oder eine große Menge an Daten haben, bevor man überhaupt einen Leistungsabfall in einem modernen Browser bemerken würde. Es ist nur interessant zu sehen, dass Operationen tendenziell weniger effizient werden, wenn man gegen den Strich arbeitet, fast so, als ob eine natürliche Entropie am Werk ist. Javascript ist eine Hochsprache und sollte effiziente Lösungen bieten, wenn wir uns an ihre Konventionen halten, so wie eine HashMap in Java eine viel natürlichere und leistungsfähigere Wahl sein wird.

Answer 2

Ich habe eine eigenständige JavaScript-Hashtabellen-Implementierung veröffentlicht, die weiter geht als die hier aufgeführten.

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

Answer 3

Beachten Sie, dass bei Java-Sammlungen "jede Art von Objekt" als Schlüssel nicht ganz richtig ist. Ja, Sie können ein beliebiges Objekt verwenden, aber wenn dieses Objekt keine guten hashcode()- und equals()-Implementierungen hat, wird es nicht gut funktionieren. Die Basisklasse Object hat eine Standardimplementierung für diese, aber für benutzerdefinierte Klassen zu arbeiten (effektiv) als hashtable Schlüssel müssen Sie sie überschreiben. Javascript hat keine Entsprechung (die ich kenne).

Um eine Hashtable in Javascript, die (effektiv) verwenden können beliebige Objekte als Schlüssel müssen Sie etwas ähnliches auf die Objekte, die Sie verwenden, zumindest wenn Sie die Performance-Gewinne einer Hashtable halten wollen erzwingen zu erstellen. Wenn Sie eine 'hashcode()'-Methode, die einen String zurückgibt erzwingen können, dann können Sie nur ein Objekt unter der Haube als die tatsächliche Hashtable verwenden.

Andernfalls müssten Sie so etwas wie die anderen Lösungen gepostet, die im Moment nicht wie Hashtabellen durchführen. Sie beide tun O(n) Suchen über die Liste, um zu versuchen, und finden Sie den Schlüssel, die ziemlich viel den Zweck einer Hashtabelle (Hashtabellen sind in der Regel konstante Zeit für get/put) besiegt.

Answer 4

Hier ist eine naive Implementierung, die ich gerade zusammengestellt habe - wie keparo in einem Kommentar erwähnte, ist eines der großen Probleme die Gleichheitsprüfung:

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;
};

Beispiel für die Verwendung:

>>> 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"

Dies ist in keiner Weise eine vollständige Implementierung, sondern nur ein Hinweis auf eine Möglichkeit, ein solches Objekt zu implementieren. Wenn man sich zum Beispiel anschaut, was ich angegeben habe, müsste man auch die Überprüfung der Konstruktoreigenschaften vor der Überprüfung der Objekteigenschaften hinzufügen, so wie es derzeit funktioniert:

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