1

Possible Duplicate:
Is there any good JavaScript hash(code/table) implementation out there?

I want a data structure that I can query a key from in O(1), delete an element rather quickly and random sample from in O(1).

I thought of a Dictionary (for the key query) combined with Array (for sampling). But is there a way to connect (pointer) between the 2?

for example: I want to delete an entry, given its key. so I can delete it easily from the dictionary, but how can I use the dictionary to splice it out of the Array?

edit:

var dict = {key1: "val1",key2:"val2"};

getting the item by key:

getKey = function(key){ return dict[key]; }

getting the item by index (which I want to change)

getIndex = function(ind) { return dict.values()[ind] }

the problem with the getIndex function is that .values() goes over all the dictionary and puts it in an array. and if the dictionary is large that is very expensive.

Update: I forgot about this question and in the meanwhile I've solved it, so here's the solution:
We can use a dictionary and an array: The array will hold all the keys of the dictionary The dictionary will hold the keys as its keys and instead of the values a tuple of where index is the index of this element's key in the array (a pointer back to the array of sort).
So this way the array points to the dictionary and the dictionary points back to the array.

Now the operations on the ds are as following:

Insert(key,value):
push a new key to the array create a tuple insert the tuple to the dictionary with key 'key'

get(key):
return dictionary.get(key)

remove(key):
remove elem from the dictionary switch between the last key in the array and our key (we have the pointer to our key) update the pointer in the dictionary to the key that was last and we've switched delete our key from the array

randomSample(sampler):
sample the array with sampler (which can be uniform sampling for example). iterate over all the samples and return the values corresponding the keys from the dictionary

The full source code of the class is available: https://gist.github.com/shacharz/9807577

4

2 回答 2

0

不太确定你想用随机样本实现什么。但据我了解，您基本上是在寻找一张可以让您掌握值列表的地图？

找到了这个：https ://stackoverflow.com/a/868728/715236

于 2012-09-15T22:26:04.680 回答
0

老实说，我不知道这个解决方案是否通过了您的性能标准，但它就在这里......这个想法的核心是使用同一个字典来存储这两个。有一些明显的缺点，包括删除生成的索引中的漏洞。查找应该非常快，这在使用良好的随机数据源时可以进行非常好的随机查找。

很难有你的蛋糕并吃掉它。绝对对此的其他解决方案感兴趣。

var dict = {key1: "val1", 0:"key1", key2:"val2", 1:"key2"};
var COUNT = 1;

// inserts
function insertValue(dictionary, key, value) {
    if (typeof dictionary[key] === 'undefined') {    
        COUNT++;
        dict[key] = value;
        dict[COUNT] = key;
    } else {
        return false;
    }
    return;
}

// return an item by index
var index = 20;
var itemByIndex = dict[dict[index]];

// updates by index
dict[dict[index]] = newValue;

// return a "random" element
function getRandomItem (dictionary, maxIndex) {
    var randomNumber = Math.floor(Math.rand() * maxIndex);
    var randomValue = dictionary[randomNumber];
    if (typeof randomValue === 'undefined') {
        return getRandomItem(dictionary, maxIndex);
    }
    return randomValue;
}

// deletes item by index
function deleteItemByIndex(dictionary, index) {
    delete dictionary[dictionary[index]];
    delete dictionary[index];
}
于 2012-09-16T02:00:27.843 回答