如何像 v8 一样实现健壮的哈希 table

Question

希望了解如何在 JavaScript.

中实现哈希 table

我希望它能够：

高效解决冲突,
space高效，并且
大小无限制（至少在原则上，就像 v8 对象一样，不超过系统内存的大小）。

根据我的研究和 SO 的帮助，有很多方法可以 resolve collisions in hash tables. The way v8 does it is Quadratic probing:

hash-table.h

wikipedia algorithm 在 JavaScript 中实现二次探测看起来像这样：

var i = 0
var SIZE = 10000
var key = getKey(arbitraryString)
var hash = key % SIZE
if (hashtable[hash]) {
  while (i < SIZE) {
    i++
    hash = (key + i * i) % SIZE
    if (!hashtable[hash]) break
    if (i == SIZE) throw new Error('Hashtable full.')
  }
  hashtable[hash] = key
} else {
  hashtable[hash] = key
}

维基百科条目中缺少的元素是：

如何计算哈希 getKey(arbitraryString)。希望了解 v8 是如何做到这一点的（不一定是精确的复制品，只是沿着相同的路线）。不精通 C 看起来 key is an object, and the hash is a 32 bit integer. Not sure if the lookup-cache.h 很重要。
如何使其动态化以便可以删除 SIZE 约束。
在哪里存储最后的 hash，以及如何多次计算它。

V8 允许您指定要在散列 table:

中使用的自己的 "Shape" 对象

// The hash table class is parameterized with a Shape.
// Shape must be a class with the following interface:
//   class ExampleShape {
//    public:
//     // Tells whether key matches other.
//     static bool IsMatch(Key key, Object* other);
//     // Returns the hash value for key.
//     static uint32_t Hash(Isolate* isolate, Key key);
//     // Returns the hash value for object.
//     static uint32_t HashForObject(Isolate* isolate, Object* object);
//     // Convert key to an object.
//     static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
//     // The prefix size indicates number of elements in the beginning
//     // of the backing storage.
//     static const int kPrefixSize = ..;
//     // The Element size indicates number of elements per entry.
//     static const int kEntrySize = ..;
//     // Indicates whether IsMatch can deal with other being the_hole (a
//     // deleted entry).
//     static const bool kNeedsHoleCheck = ..;
//   };

但不确定密钥是什么以及他们如何将该密钥转换为散列以便密钥均匀分布并且散列函数不仅仅是一个 hello-world 示例。

问题是，如何实现像V8一样的快速散列table，既能高效解决冲突又无大小限制。它不必完全像 V8，但具有上面概述的功能。

就 space 效率 而言，一种天真的方法会 var array = new Array(10000)，这会占用大量内存，直到它被填满。不确定 v8 如何处理它，但如果你 var x = {} 多次，它不会为未使用的键分配一堆内存，不知何故它是动态的。

我基本上被困在这里：

var m = require('node-murmurhash')

function HashTable() {
  this.array = new Array(10000)
}

HashTable.prototype.key = function(value){
  // not sure if the key is actually this, or
  // the final result computed from the .set function,
  // and if so, how to store that.
  return m(value)
}

HashTable.prototype.set = function(value){
  var key = this.key(value)
  var array = this.array
  // not sure how to get rid of this constraint.
  var SIZE = 10000
  var hash = key % SIZE
  var i = 0
  if (array[hash]) {
    while (i < SIZE) {
      i++
      hash = (key + i * i) % SIZE
      if (!array[hash]) break
      if (i == SIZE) throw new Error('Hashtable full.')
    }
    array[hash] = value
  } else {
    array[hash] = value
  }
}

HashTable.prototype.get = function(index){
  return this.array[index]
}

Answer 1

这是一个非常宽泛的问题，我不确定您想要得到什么答案。（"How to implement ...?" 听起来您只是希望有人为您完成工作。请更具体一些。）

How to compute the hash

任何散列函数都可以。我已经在您提出的另一个问题中指出了 V8 的实现；但你在这里真的有很多自由。

Not sure if the lookup-cache.h is important.

不，这无关。

How to make it dynamic so the SIZE constraint can be removed.

将 table 的当前大小存储为变量，跟踪散列中元素的数量 table，并在使用的插槽百分比时增加 table超过给定的阈值（你有一个 space-time tradeoff 那里：较低的负载因子如 50% 会产生较少的冲突但使用更多的内存，较高的因子如 80% 使用较少的内存但遇到更慢的情况）。我将从估计容量 "minimum number of entries you'll likely need" 开始，然后以 2 倍的步长增长（例如 32 -> 64 -> 128 -> 等）。

Where to store the final hash,

这很难：在 JavaScript 中，您不能在字符串（或一般的原语）上存储额外的属性。您可以在旁边使用 Map（或对象），但如果您无论如何都要这样做，那么您不妨将其用作 the 散列 table，而不是费心在上面实现你自己的东西。

and how to compute it more than once.

这很简单：再次调用您的散列函数 ;-)

I just want a function getUniqueString(string)

这个怎么样：

var table = new Map();
var max = 0;

function getUniqueString(string) {
  var unique = table.get(string);
  if (unique === undefined) {
    unique = (++max).toString();
    table.set(string, unique);
  }
  return unique;
}

为了更好的封装，您可以定义一个具有 table 和 max 作为属性的对象。

如何像 v8 一样实现健壮的哈希 table

How to implement a robust hash table like v8

javascript

hash

v8

hashtable

data-structures