JavaScript-Hashmap-Äquivalent

Question

Wie bereits in Update 3 über diese Antwort diese Notation:

var hash = {};
hash[X]

das Objekt nicht wirklich hasht X ; es wandelt eigentlich nur um X zu einer Zeichenkette (über .toString() wenn es sich um ein Objekt handelt, oder einige andere eingebaute Konvertierungen für verschiedene primitive Typen) und sucht dann diese Zeichenkette, ohne sie zu hashen, in " hash ". Auch die Objektgleichheit wird nicht überprüft - wenn zwei verschiedene Objekte die gleiche Stringkonvertierung haben, überschreiben sie sich einfach gegenseitig.

Angesichts dieser - gibt es eine effiziente Implementierungen von Hashmaps in JavaScript?

(Zum Beispiel, das zweite Google-Ergebnis von javascript hashmap führt zu einer Implementierung, die für jede Operation O(n) ist. Verschiedene andere Ergebnisse ignorieren die Tatsache, dass verschiedene Objekte mit äquivalenten Zeichenkettendarstellungen sich gegenseitig überschreiben.

Answer 1

Das sieht nach einem ziemlich robusten Lösung aus: https://github.com/flesler/hashmap

Es funktioniert sogar bei Funktionen und Objekten, die identisch aussehen. Der einzige Hack, der verwendet wird, ist das Hinzufügen eines obskuren Mitglieds zu einem Objekt, um es zu identifizieren. Wenn Ihr Programm diese obskure Variable nicht überschreibt (es ist etwas wie hashid ), sind Sie auf der sicheren Seite.

Answer 2

Eine weitere Kartenimplementierung von mir. Mit randomizer, 'generics' und 'iterator' =)

var HashMap = function (TKey, TValue) {
    var db = [];
    var keyType, valueType;

    (function () {
        keyType = TKey;
        valueType = TValue;
    })();

    var getIndexOfKey = function (key) {
        if (typeof key !== keyType)
            throw new Error('Type of key should be ' + keyType);
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return i;
        }
        return -1;
    }

    this.add = function (key, value) {
        if (typeof key !== keyType) {
            throw new Error('Type of key should be ' + keyType);
        } else if (typeof value !== valueType) {
            throw new Error('Type of value should be ' + valueType);
        }
        var index = getIndexOfKey(key);
        if (index === -1)
            db.push([key, value]);
        else
            db[index][1] = value;
        return this;
    }

    this.get = function (key) {
        if (typeof key !== keyType || db.length === 0)
            return null;
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return db[i][1];
        }
        return null;
    }

    this.size = function () {
        return db.length;
    }

    this.keys = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.push(db[i][0]);
        }
        return result;
    }

    this.values = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.push(db[i][1]);
        }
        return result;
    }

    this.randomize = function () {
        if (db.length === 0)
            return this;
        var currentIndex = db.length, temporaryValue, randomIndex;
        while (0 !== currentIndex) {
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex--;
            temporaryValue = db[currentIndex];
            db[currentIndex] = db[randomIndex];
            db[randomIndex] = temporaryValue;
        }
        return this;
    }

    this.iterate = function (callback) {
        if (db.length === 0)
            return false;
        for (var i = 0; i < db.length; i++) {
            callback(db[i][0], db[i][1]);
        }
        return true;
    }
}

Beispiel:

var a = new HashMap("string", "number");
a.add('test', 1132)
 .add('test14', 666)
 .add('1421test14', 12312666)
 .iterate(function (key, value) {console.log('a['+key+']='+value)});
/*
a[test]=1132
a[test14]=666
a[1421test14]=12312666 
*/
a.randomize();
/*
a[1421test14]=12312666
a[test]=1132
a[test14]=666
*/