Par*_*roX 11 javascript node.js
我期待为二进制四键实现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哈希表和2 INT32.第一个键是前4个字节,第二个键是最后4个字节.它不像1次操作查找那样理想找到一个值,但是2次操作仍然足够好.
但是,如果所有键都存储为字符串,或者所有数字都是双精度浮点格式数字(8字节),那么我认为这不值得,因此每个哈希条目将占用16个字节(两个" int32"数字).
我的问题是:
1.如果存储一个数字作为属性的键,是否会占用8个字节的内存,或者它会转换为字符串并占用长度*2字节？
PS:我用nodejs标记这个,因为可能存在可以帮助我最终目标的库
编辑1:
似乎1Map()和节点0.12.x + 是可能的
至于数字2,我能够使用int64 lib(bytebuffer)并将64int转换为缓冲区.
我想只使用缓冲区作为Map()的键,但它不会让我因为缓冲区内部是一个对象,每个实例都充当Map()的新键.
所以我考虑将缓冲区恢复为原生类型,64位双倍.
使用readDoubleBE我读取缓冲区作为double,它代表我的64int二进制文件并成功让我在地图中使用它并允许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我能够看到最大堆大小为497962856字节,此方法使用Set(),而在Set()中使用字符串为1111082864字节.这大概是500MB对1GB,这与80mb和230mb相差甚远,不确定额外的内存使用来自何处.对于我使用的这些内存测试来说,它没有任何价值Set,Map因为它应该只在数据结构中存储唯一键.(使用Set作为存在检查器,Map将用作查找)
您的节点版本中的内存从Map到加倍来自于糟糕的实现。Set好吧，本身并不是“坏” ，只是不适合数百万个条目。更简单的处理是Set通过记忆购买的。天下没有免费的午餐，一如既往，抱歉。
为什么他们一般使用这么多？它们应该处理任何对象，而能够处理所有可能的种类的方法非常昂贵。如果您拥有的所有内容都是一种类型，则可以进行优化，但您必须对其进行检查，并且在 99,99% 的情况下，不值得这么麻烦，因为映射、集合和数组都很短，只有几千个条目最多。平淡地说：开发人员的时间很昂贵，最好花在其他地方。我可以补充一点：它是开源的，你自己做吧！但我知道说起来容易做起来难;-)
你需要自己卷起来。您可以使用 aUint32Array并围绕它构建一个哈希表。
根据MS和四键描述， Bing-Map 使用 4 进制数字字符串（最多 23 个）进行编码。使用后者的编码（没有读过前者，所以细节上可能有错误）我们可以将其放入两个32位整数：
function quadToInts(quad, zoom){
var high,low, qlen, i, c;
high = 0>>>0;
low = 0>>>0
zoom = zoom>>>0;
// checks & balances omitted!
qlen = quad.length;
for(i = 0; i < 16 && i < qlen ;i++){
c = parseInt(quad.charAt(i));
high |= c << (32-(i*2 + 2));
}
// max = 23 characters (says MS)
for(i = 0; i < 8 && i < qlen - 16 ;i++){
c = parseInt(quad.charAt(16 + i));
low |= c << (32-(i*2 + 2));
}
low |= zoom;
return [high,low];
}
然后回来
// obligatory https://graphics.stanford.edu/~seander/bithacks.html
function rev(v){
var s = 32;
var mask = (~0)>>>0;
while ((s >>>= 1) > 0) {
mask ^= (mask << s)>>>0;
v = ((v >>> s) & mask) | ((v << s) & (~mask)>>>0);
}
return v;
}
function intsToQuad(k1,k2){
var r, high, low, zoom, c, mask;
r = "";
mask = 0x3; // 0b11
high = k1>>>0;
low = k2>>>0;
zoom = low & (0x20 - 1);
low ^= zoom;
high = rev(high);
for(var i = 0;i<16;i++){
c = high & mask;
c = (c<<1 | c>>>1) & mask;
r += c.toString(10);
high >>>= 2;
}
low = rev(low);
for(var i = 0;i<16;i++){
c = low & mask;
c = (c<<1 | c>>>1) & mask;
r += c.toString(10);
low >>>= 2;
}
return [r,zoom];
}
（所有快速技巧，请在使用前检查！C&P 魔鬼也可能在这里插手）
基于以下哈希函数的哈希表的粗略草图
// shamelessly stolen from http://www.burtleburtle.net/bob/c/lookup3.c
function hashword(k1, // high word of 64 bit value
k2, // low word of 64 bit value
seed // the seed
){
var a,b,c;
var rot = function(x,k){
return (((x)<<(k)) | ((x)>>>(32-(k))));
};
/* Set up the internal state */
a = b = c = 0xdeadbeef + ((2<<2)>>>0) + seed>>>0;
if(arguments.length === 2){
seed = k1^k2;
}
b+=k2;
a+=k1;
c ^= b; c -= rot(b,14)>>>0;
a ^= c; a -= rot(c,11)>>>0;
b ^= a; b -= rot(a,25)>>>0;
c ^= b; c -= rot(b,16)>>>0;
a ^= c; a -= rot(c,4)>>>0;
b ^= a; b -= rot(a,14)>>>0;
c ^= b; c -= rot(b,24)>>>0;
return c;
}
function hashsize(N){
var highbit = function(n) {
var r = 0 >>> 0;
var m = n >>> 0;
while (m >>>= 1) {
r++;
}
return r;
};
return (1<<(highbit(N)+1))>>>0;
}
function hashmask(N){
return (hashsize(N)-1)>>>0;
}
以及表处理的（相当不完整的）代码
/*
Room for 8-byte (64-bit) entries
Table pos. Array pos.
0 0 high, low
1 2 high, low
2 4 high, lowl
...
n n*2 high, low
*/
function HashTable(N){
var buf;
if(!N)
return null;
N = (N+1) * 2;
buf = new ArrayBuffer(hashsize(N) * 8);
this.table = new Uint32Array(buf);
this.mask = hashmask(N);
this.length = this.table.length;
}
HashTable.prototype.set = function(s,z){
var hash, quad, entry, check, i;
entry = null;
quad = quadToInts(s,z);
hash = hashword(quad[0],quad[1]);
entry = hash & this.mask;
check = entry * 2;
if(this.table[check] != 0 || this.table[check + 1] != 0){
//handle collisions here
console.log("collision in SET found")
return null;
} else {
this.table[check] = quad[0];
this.table[check + 1] = quad[1];
}
return entry;
};
HashTable.prototype.exists = function(s,z){
var hash, quad, entry, check, i;
entry = null;
quad = quadToInts(s,z);
hash = hashword(quad[0],quad[1]);
entry = hash & this.mask;
check = entry * 2;
if(this.table[check] != 0 || this.table[check + 1] != 0){
return entry;
}
return -1;
};
HashTable.prototype.get = function(index){
var entry = [0,0];
if(index > this.length)
return null;
entry[0] = this.table[index * 2];
entry[1] = this.table[index * 2 + 1];
return entry;
};
// short test
var ht = new HashTable(100);
ht.set("01231031020112310",17);
ht.set("11231031020112311",12);
ht.set("21231033020112310",1);
ht.set("31231031220112311321312",23);
var s = "";
for(var i=0;i<ht.table.length;i+=2){
if(ht.table[i] !== 0){
var e = intsToQuad(ht.table[i],ht.table[i+1]);
s += e[0] +", " +e[1] + "\n";
}
}
console.log(s)
碰撞应该很少见，因此几个短的标准数组就可以捕获它们。为了处理它，您需要在代表 Quad 的两个整数的 8 个字节中添加另一个字节，或者更好的方法是将第二个整数设置为全 1（Quad 不会发生这种情况），将第一个整数设置为中的位置碰撞数组。
添加有效负载有点复杂，因为您只有固定的长度来执行此操作。
我已将表的大小设置为下一个较高的 2 的幂。这可能太多了，甚至太多了，您可能会想调整它，所以请注意，掩蔽不再按预期工作，您需要进行取模。