Hashtable的64位整数

Question

我期待实现的O（1）查找为binary quadkeys

我知道有是Javascript没有真正的哈希表，而不是使用对象和O（1）查找与它们的属性，但问题在于键总是转换为字符串。

我怀疑有超过1000万的条目在内存中，如果我不得不依赖键是字符串，并且平均quadkey字符串是11.5个字符，相当于（1000万条记录* 11.5长度* 2个字节） = 230,000,000字节或230 MB。

相比存储为Int64的（10万个条目* 8个字节）= 80000000个字节或80 MB

我知道的Int64不使用JavaScript原生支持，但也有可能与协助的术语库做我想要的按位操作。

现在，尽管存在可以处理int64的库，它们最终是不是真正代表8个字节的对象，所以我相信我不能在散列表中使用任何int64库，而是考虑使用2-depth哈希表与两个int32。第一个键是前4个字节，第二个键是最后4个字节。它不如1次操作查找找到一个值，但2次操作仍然足够好。但是，如果所有的键都存储为字符串，或者所有数字都是双精度浮点格式数字（8字节），那么每个散列条目将占用16个字符的事实，我觉得这是不值得的字节（两个“int32”数字）。

我的问题是：

1.如果您存储号码为重点，以一个属性，它会占用8个 字节的内存或将其转换为字符串，并采取了 长度* 2字节？

是否有二进制quadkeys编码到双精度 浮点格式数目的标准的方式，JavaScript的已通过， 即使号码是没有意义的，则基础位提供了一个 目的（唯一标识一个构造）。

PS：我纪念这一具有的NodeJS因为有可能存在，可以帮助我的最终目标库

---

编辑1：

似乎是可能的Map()和节点0.12.x +

至于我能够使用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的varints，这样我可以节省更多的内存，但我不确定这是否可能在Map中，因为我无法使用缓冲区作为关键字。

---

编辑2：

使用memwatch-next我能看到，最大堆大小为497962856个字节，这种方法与设置（），而使用集的字符串（）为1111082864个字节。那大约是500MB和1GB，这与80MB和230MB相差甚远，不知道额外内存使用的来源。对于这些内存测试，我使用Set而不是Map这种方式，它应该只存储数据结构中唯一的密钥。 （使用Set作为存在检查器，其中Map将用作查找）

Answer 1

从内存中Map到Set在你的节点的版本加倍来自一个坏实现。那么，不是“坏”本身只是不适合数百万条目。更简单的处理Set获取与记忆。没有免费的午餐，一如既往，对不起。

为什么他们一般使用这么多？他们应该处理任何对象和方法能够处理所有可能的品种是真的昂贵。如果你拥有的只有一种，但是你必须检查它，并且在99.99％的情况下它是不值得的，因为它可以被优化，因为地图和集合和数组都很短，几千条最。平淡无奇：开发人员的时间是昂贵的，而且更好地花在别处。我可以补充：它是开源的，自己动手！但我知道说起来容易做起来难;-)

你需要自己推出它。你可以使用Uint32Array来构建一个哈希表。

根据MS和Quad-key description，Bing-Maps使用基数为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("",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上）和第一个到位置碰撞阵列。

添加有效负载有点复杂，因为您只有固定长度才能这样做。

我已经将表的大小设置为下一个更高的幂。这可能太多，甚至太多太多了，你可能会试图去适应它，所以要注意，掩模不能按预期工作，你需要做一个模数转换。

Answer 2

因为您的键是整数（并且是唯一的），所以可以将它们用作数组索引。但是，JS数组被限制为包含由32或64位整数限定的最大条目，具体取决于您的平台。

为了克服这个问题，你可以使用你的两步法，但不使用对象和它们的字符串散列。你可以存储它是这样的 store[0010][1000] = 'VALUE' - 二进制键00101000项目被存储在索引0010在第一阵列和索引1000儿童阵列

在小数，你处理store[2][8] = 'VALUE'，这相当于做store[40] = 'VALUE'在64位空间

你让自己所有的属性一棵树你想：

• 您可以轻松地通过键查找（分两步）
• 你的钥匙是整数
• 你处理的32位整数（或更低，这取决于你如何块吧）