哈希表如何确保对象键被散列到 JavaScript 中的唯一索引中

Question

查看 JavaScript 中的简单 hash table implementation 后，关键索引计算为：

function index(str, max) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    var letter = str[i];
    hash = (hash << 5) + letter.charCodeAt(0);
    hash = (hash & hash) % max;
  }
  return hash;
}

所以我想知道在 v8 的情况下，它如何使用类似的函数但确保索引在对象上是唯一的。所以如果你这样做：

{ a: 'foo', b: 'bar' }

然后变成这样：

var i = index('a', 100000)
// 97
var j = index('b', 100000)
// 98

但是，如果您在一个对象上有 100 个或 1000 个或更多键，则似乎可能会发生冲突。

想知道哈希表如何保证它们是唯一的，以 v8 为例。

Answer 1

这里是 V8 开发人员。字符串的散列不是唯一的（这就是使用散列函数的意义所在）； V8 使用二次探测来处理碰撞（参见 source). You can read more about various strategies at https://en.wikipedia.org/wiki/Hash_table#Collision_resolution.

另外，hash = (hash & hash) % max; 很傻 ;-)

哈希表如何确保对象键被散列到 JavaScript 中的唯一索引中

How hashtable makes sure object keys are hashed into a unique index in JavaScript

javascript

hashtable

unique