在这个答案的更新3中已经明确表示,这个符号:

var hash = {};
hash[X]

实际上并不散列对象X;它实际上只是将X转换为一个字符串(如果它是一个对象,则通过. tostring(),或者其他一些用于各种基本类型的内置转换),然后在“哈希”中查找该字符串,而不散列它。对象相等性也不检查-如果两个不同的对象具有相同的字符串转换,它们将相互覆盖。

鉴于此,JavaScript中是否有有效的hashmap实现?

(例如,javascript hashmap的第二个谷歌结果对任何操作产生的实现都是O(n)。其他各种结果忽略了具有等效字符串表示的不同对象会相互覆盖这一事实。


当前回答

根据ECMAScript 2015 (ES6),标准JavaScript有一个Map实现。更多信息可以在这里找到。

基本用法:

var myMap = new Map();
var keyString = "a string",
    keyObj = {},
    keyFunc = function () {};

// Setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");

myMap.size; // 3

// Getting the values
myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"

其他回答

我的“地图”实现,源自Christoph的例子:

使用示例:

var map = new Map();  // Creates an "in-memory" map
var map = new Map("storageId");  // Creates a map that is loaded/persisted using html5 storage

function Map(storageId) {
    this.current = undefined;
    this.size = 0;
    this.storageId = storageId;
    if (this.storageId) {
        this.keys = new Array();
        this.disableLinking();
    }
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// Map initialisation from an existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;
    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }
    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;

    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
//    this.removeAll = Map.illegal;


    return this;
};

// Overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- Mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    if (item === undefined) {
        if (this.storageId) {
            try {
                var itemStr = localStorage.getItem(this.storageId + key);
                if (itemStr && itemStr !== 'undefined') {
                    item = JSON.parse(itemStr);
                    this[this.hash(key)] = item;
                    this.keys.push(key);
                    ++this.size;
                }
            } catch (e) {
                console.log(e);
            }
        }
    }
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;
    if (this.storageId) {
        this.keys.push(key);
        try {
            localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
        } catch (e) {
            console.log(e);
        }
    }
    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];
    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }
    if (this.storageId) {
        try {
            localStorage.setItem(this.storageId + key, undefined);
        } catch (e) {
            console.log(e);
        }
    }
    return this;
};

// Only works if linked
Map.prototype.removeAll = function() {
    if (this.storageId) {
        for (var i=0; i<this.keys.length; i++) {
            this.remove(this.keys[i]);
        }
        this.keys.length = 0;
    } else {
        while(this.size)
            this.remove(this.key());
    }
    return this;
};

// --- Linked list helper functions

Map.prototype.link = function(item) {
    if (this.storageId) {
        return;
    }
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if (this.storageId) {
        return;
    }
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- Iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    if (this.storageId) {
        return undefined;
    } else {
        return this.current.key;
    }
};

Map.prototype.value = function() {
    if (this.storageId) {
        return undefined;
    }
    return this.current.value;
};

在ECMAScript 6中,你可以使用WeakMap。

例子:

var wm1 = new WeakMap(),
    wm2 = new WeakMap(),
    wm3 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // A value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // Keys and values can be any objects. Even WeakMaps!

wm1.get(o2); // "azerty"
wm2.get(o2); // Undefined, because there is no value for o2 on wm2
wm2.get(o3); // Undefined, because that is the set value

wm1.has(o2); // True
wm2.has(o2); // False
wm2.has(o3); // True (even if the value itself is 'undefined')

wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // Undefined, because wm3 was cleared and there is no value for o1 anymore

wm1.has(o1);   // True
wm1.delete(o1);
wm1.has(o1);   // False

But:

因为引用是弱的,WeakMap键是不可枚举的(也就是说,没有方法给你一个键的列表)。

不幸的是,之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此,我写了一个简单的类似java的HashMap版本:

function HashMap() {
    this.buckets = {};
}

HashMap.prototype.put = function(key, value) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        bucket = new Array();
        this.buckets[hashCode] = bucket;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            bucket[i].value = value;
            return;
        }
    }
    bucket.push({ key: key, value: value });
}

HashMap.prototype.get = function(key) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        return null;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            return bucket[i].value;
        }
    }
}

HashMap.prototype.keys = function() {
    var keys = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            keys.push(bucket[i].key);
        }
    }
    return keys;
}

HashMap.prototype.values = function() {
    var values = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            values.push(bucket[i].value);
        }
    }
    return values;
}

注意:键对象必须“实现”hashCode()和equals()方法。

这是我的另一个地图实现。使用randomizer, 'generics'和'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;
    }
}

例子:

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
*/

JavaScript没有内置的map/hashmap。它应该被称为关联数组。

hash["X"]等于hash。X,但它允许“X”作为字符串变量。 换句话说,hash[x]在函数上等于eval("hash."+x. tostring())。

它更类似于object。属性而不是键值映射。 如果你在JavaScript中寻找一个更好的键/值映射,请使用Map对象。