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位整數（或更低，這取決於你如何塊吧）