javascript结合了数组和字典

javascript combine array and dictionary

本文关键字：字典 数组 结合了 javascript      更新时间：2023-09-26

可能重复：
有什么好的JavaScript散列（代码/表）实现吗？

我想要一个数据结构，我可以在O（1）中查询关键字，相当快速地删除元素，并在O（2）中随机采样。

我想到了Dictionary（用于关键字查询）与Array（用于采样）相结合。但是有没有办法在2之间连接（指针）？

例如：我想删除一个条目，给定它的关键字。所以我可以很容易地从字典中删除它，但我如何使用字典将它从数组中拼接出来？

编辑：

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

按密钥获取项目：

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

按索引获取项目（我想更改）

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

getIndex函数的问题是.values（）遍历所有字典并将其放入数组中。如果字典很大，那就很贵。

更新：我忘记了这个问题，同时我已经解决了它，所以下面是解决方案：
我们可以使用字典和数组：数组将包含字典的所有关键字字典将保存键作为其键，而不是值，其中index是数组中该元素键的索引的元组（指向排序数组的指针）
通过这种方式，数组指向字典，字典指向数组。

现在ds上的操作如下：

插入（键，值）：
向数组中添加新键创建元组使用关键字"key"将元组插入字典

get（key）：
return dictionary.get（key）

移除（密钥）：
从字典中删除elem在数组中的最后一个键和我们的键之间切换（我们有指向键的指针）将字典中的指针更新为最后一个键，我们已经切换从阵列中删除我们的密钥

randomSample（采样器）：
使用采样器对阵列进行采样（例如，可以是均匀采样）。对所有样本进行迭代，并返回字典中与关键字对应的值

该类的完整源代码可用：https://gist.github.com/shacharz/9807577

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

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

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

既要有蛋糕又要吃它是很困难的。当然对其他解决方案感兴趣。

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];
}
相关文章：