javascript - 具有 64 位整数的哈希表

Question

我希望为 binary quadkeys 实现 O(1) 查找

我知道 javascript 没有真正的哈希表，而是使用对象和 o(1) 查找及其属性，但问题是键总是转换为字符串。

我怀疑内存中有超过 1000 万个条目，如果我必须依赖作为字符串的键并且平均四键字符串为 11.5 个字符，则等于(1000 万个条目 * 11.5 长度 * 2 个字节)= 230,000,000 字节或 230 MB。

与存储为 int64(1000 万个条目 * 8 字节)= 80,000,000 字节或 80 MB 相比

我知道 javascript 本身不支持 int64，但是有一些库可以在执行我想要的按位运算方面提供帮助。

现在，即使存在可以处理 int64 的库，但它们最终是不能真正代表 8 个字节的对象，所以我相信我不能在哈希表中使用任何 int64 库，而是我正在考虑使用 2-deep hash有两个 int32 的表。第一个键是前 4 个字节，第二个键是最后 4 个字节。查找值不如 1 次操作查找理想，但 2 次操作仍然足够好。

但是，如果所有键都存储为字符串，或者所有数字都是 double 浮点格式数字(8 个字节)，那么我觉得这是不值得的，因此每个哈希条目将占用 16 个字节(两个“int32”数字)。

我的问题是:

1.如果存储一个数字作为属性的key，会不会占用8 字节的内存还是会转换为字符串并占用 长度*2字节？

1. 有没有办法将二进制四键编码为 double javascript采用的浮点格式数字标准，即使这个数字没有意义，底层的比特也可以作为目的(构造的唯一标识)。

PS:我用 nodejs 标记它，因为可能存在可以帮助我实现最终目标的库

---

编辑1:

似乎 1 可以使用 Map() 和 Node 0.12.x+

就数字 2 而言，我能够使用 int64 库 (bytebuffer) 并将 64int 转换为缓冲区。

我只想将缓冲区用作 Map() 的键，但它不允许我这样做，因为缓冲区在内部是一个对象，每个实例都充当 Map() 的新键。

所以我考虑将缓冲区转回 native 类型，即 64 位 double 。

使用 readDoubleBE 我将缓冲区读取为 double ，它表示我的 64int 二进制文件，并成功地让我在 map 中使用它并允许 O(1) 查找。

var ByteBuffer = require("bytebuffer");

var lookup = new Map();


var startStr = "123123738232777";
for(var i = 1; i <= 100000; i++) {
    var longStr = startStr + i.toString();
    var longVal = new ByteBuffer.Long.fromValue(longStr);

    var buffer = new ByteBuffer().writeUint64(longVal).flip().toBuffer();
    var doubleRepresentation = buffer.readDoubleBE();
    lookup.set(doubleRepresentation, longStr);
}

console.log(exists("12312373823277744234")); // true
console.log(exists("123123738232777442341232332322")); // false


function exists(longStr) {
    var longVal = new ByteBuffer.Long.fromValue(longStr);
    var doubleRepresentation = new ByteBuffer().writeUint64(longVal).flip().toBuffer().readDoubleBE();
    return lookup.has(doubleRepresentation);
}

代码草率，我可能缺少快捷方式，因此欢迎任何建议/提示。

理想情况下，我想利用 bytebuffer 的 varint 来节省更多内存，但我不确定这在 Map 中是否可行，因为我无法使用缓冲区作为键。

---

编辑 2:

使用 memwatch-next使用 Set() 的这种方法，我能够看到最大堆大小为 497962856 字节，而在 Set() 中使用字符串为 1111082864 字节。这大约是 500MB 与 1GB，与 80mb 和 230mb 相差甚远，不确定额外的内存使用来自哪里。对于我使用 Set 而不是 Map 的这些内存测试毫无值(value)，因为它应该只在数据结构中存储唯一键。 (使用 Set 只是一个存在检查器，其中 Map 将用作查找)

Answer 1

因为您的键是整数(并且是唯一的)，您可以将它们用作数组索引。但是，根据您的平台，JS 数组被限制为包含以 32 位或 64 位整数为界的最大条目。

要克服这个问题，您可以使用两步法，但不使用对象及其字符串哈希。你可以像这样存储它 store[0010][1000] = 'VALUE' - 带有二进制 key 的项目00101000存储在索引 0010 下在第一个数组和索引中 1000在子数组中

以十进制表示，您正在处理 store[2][8] = 'VALUE' ，相当于做store[40] = 'VALUE'在 64 位空间中

你会得到一棵树，里面有你想要的所有属性:

• 您可以通过按键轻松查找(分两步)
• 您的键是整数
• 您正在处理 32 位整数(或更少，取决于您如何分 block )