64位整数散列表
我正在寻找实现二进制quadkeys O（1）查找
我知道，没有JavaScript的真正的散列表，而是使用对象和o（1）查找与他们的属性，但问题是，键总是转换为string。
我怀疑有超过一千万的内存条目，如果我不得不依赖于键是string和平均quadkeystring是11.5个字符，相当于（1000万条* 11.5长度* 2个字节）= 230,000,000字节或230 MB。
与存储为int64（1000万条logging* 8字节）= 80,000,000字节或80 MB相比
我知道int64本身不支持javascript，但是有些库可以帮助我进行按位操作。
现在，即使存在可以处理int64的库，它们最终也不是真正代表8个字节的对象，所以我相信我不能在散列表中使用任何int64库，而是考虑使用2深度哈希表INT32。 第一个键是前4个字节，第二个键是最后4个字节。 它不如1次操作查找find一个值，但2次操作仍然足够好。
但是，如果所有的键都存储为string，或者所有的数字都是双精度浮点格式的数字（8字节），那么每个散列条目占用16个字节（两个“ int32“数字）。
我的问题是：
1.如果存储一个数字作为属性的关键字，它会占用8个字节的内存还是会转换为string并占用长度* 2字节？
- 有没有一种方法可以将二进制quadkeys编码为javascript采用的双精度浮点格式数字标准，即使数字没有意义，底层位也是一个用途（对结构的唯一标识）。
PS：我正在用nodejs来标记，因为可能存在的库可能有助于我的最终目标
编辑1：
似乎1可能与Map()和节点0.12.x +
至于数字2，我能够使用int64 lib（ bytebuffer ）并将64int转换为缓冲区。
我只想使用缓冲区作为Map（）的键，但它不会让我作为缓冲区内部的一个对象，其中每个实例充当Map（）的新键。
所以我考虑把缓冲区变成原生types，一个64位双。
使用readDoubleBE我读取缓冲区作为一个双重，它代表我的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); }
代码是马虎，可能有快捷键我缺less，所以任何build议/提示是欢迎的。
理想情况下，我想利用bytebuffer的varints，这样我可以节省更多的内存，但我不确定这是否可能在Map中，因为我无法使用缓冲区作为关键字。
编辑2：
使用memwatch-next，我可以看到最大堆大小是497962856字节与此方法与Set（），而在Set（）中使用string是1111082864字节。 那大概是500MB和1GB，这跟80MB和230MB差不多，不知道多余的内存来自哪里。 对于这些使用Set over Map内存testing，这种方式应该只存储数据结构中唯一的键。 （使用Set作为一个存在检查器，其中Map将用作查找）
在您的节点版本中从Map到Set内存翻倍是来自不好的实现。 那么，不是“坏” 本身不适合数以百万计的条目。 Set的更简单的处理用内存购买。 没有免费的午餐，一如既往，对不起。
为什么他们一般使用这么多？ 他们应该处理任何对象，并能够处理所有可能的品种的方法是非常昂贵的。 如果你所拥有的只是一种，但是你必须检查它是可能的，在99,99％的情况下，这是不值得的，因为地图和集合和数组是短的，几千条最。 平淡无奇：开发者的时间是昂贵的，更好地花在其他地方。 我可以补充一下：这是开源的，自己动手吧！ 但我知道说起来容易做起来难;-)
你需要自己滚动。 你可以使用Uint32Array来构build一个哈希表。
根据MS和Quad-key描述 ，Bing-Maps使用基数为4位的string（最多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 ... nn*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)
碰撞应该是罕见的，所以有一些短的标准arrays可以抓住它们。 要处理它，你需要添加另一个字节的8个字节为两个整数代表四或更好的，设置第二个整数为所有的（不会发生与四）和第一个位置（s）在碰撞arrays。
添加有效负载有点复杂，因为你只有固定的长度。
我已经把桌子的大小设置成了两个更高的幂。 这可能是太多，甚至waaay太多，你可能会试图适应它，所以要注意的是，掩盖不能按预期工作，你需要做一个模数。
因为你的键是整数（而且是唯一的），所以你可以用它们作为数组索引。 但是，JS数组被限制为包含由32或64位整数限定的最大条目，具体取决于您的平台。
为了克服这个问题，你可以使用你的两步法，但不使用对象和它们的string散列。 您可以将其存储为像这样的store[0010][1000] = 'VALUE' – 具有二进制密钥00101000的项目被存储在第一数组中的索引0010和子数组中的索引1000
在十进制中，你正在处理store[2][8] = 'VALUE' ，这相当于在64位空间中执行store[40] = 'VALUE'
你得到一棵树，拥有你想要的所有属性：
- 你可以很容易地按键查找（分两步）
- 你的钥匙是整数
- 你正在处理32位整数（或更less，取决于你如何组块）