Hashtable с 64-битными целыми числами

Ответ 1

Удвоение в памяти от Map до Set в вашей версии node происходит из-за плохой реализации. Ну, не "плохо", как таковое, просто не подходит для миллионов записей. Более простая обработка Set приобретается с памятью. Там нет бесплатного обеда, как всегда, извините.

Почему они так много используют? Они должны обрабатывать любой объект, и метод, позволяющий обрабатывать все возможные варианты, действительно дорог. Можно оптимизировать, если все, что у вас есть, имеет один вид, но вы должны его проверить, и в 99,99% всех случаев это не стоит хлопот, потому что карты и наборы и массивы коротки, несколько тысяч записей на большинство. Быть мягким: время разработчика дорого и лучше тратить в другом месте. Я мог бы добавить: это с открытым исходным кодом, сделай это сам! но я знаю, что это проще сказать, чем сделать, -)

Вам нужно бросить это самостоятельно. Вы можете использовать Uint32Array для этого и построить вокруг него таблицу хешей.

Bing-Maps кодируются строками базовых 4 цифр (не более 23) в соответствии с MS и Четырехзначное описание. Используя кодировку последнего (не прочитав первого, так что это может быть неправильно в деталях), мы можем поместить его в два 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)

Столкновения должны быть редкими, поэтому пара коротких стандартных массивов сделает их поймать. Чтобы справиться с этим, вам нужно добавить еще один байт в 8 байтов для двух целых чисел, представляющих Quad, или, лучше, установить второе целое число для всех (не будет с Quad), а первое - в позиции (-ы) в массив столкновения.

Добавление полезной нагрузки немного сложнее, потому что у вас есть только фиксированная длина.

Я установил размер таблицы для следующей более высокой мощности двух. Это может быть слишком много или даже слишком велико, и у вас может возникнуть соблазн адаптировать его, поэтому имейте в виду, что маскировка не работает так, как ожидалось, больше вам нужно сделать по модулю.

Ответ 2

Поскольку ваши ключи являются целыми числами (и являются уникальными), вы можете просто использовать их в качестве индексов массива. Однако массивы JS ограничены, чтобы содержать максимальные записи, ограниченные 32 или 64-битным целым числом в зависимости от вашей платформы.

Чтобы преодолеть это, вы можете использовать двухэтапный подход, но без использования объектов и их хэш-строк. Вы можете сохранить что-то вроде этого store[0010][1000] = 'VALUE' - элемент с двоичным ключом 00101000 хранится в индексе 0010 в первом массиве и индексе 1000 в дочернем массиве

В десятичной форме вы имеете дело с store[2][8] = 'VALUE', что эквивалентно выполнению store[40] = 'VALUE' в 64-битном пространстве

Вы получаете дерево со всеми необходимыми свойствами:

• Вы можете легко найти ключ (в два этапа)
• Ваши ключи целые числа
• Вы имеете дело с 32-битными целыми числами (или меньше, в зависимости от того, как вы его блокируете)