哈希表如何确保对象键被哈希到JavaScript中的唯一索引中 [英] How hashtable makes sure object keys are hashed into a unique index in JavaScript

问题描述

在JavaScript中查看了一个简单的哈希表实现后，密钥索引的计算方式为:

After looking at a simple hash table implementation in JavaScript, the key index is computed as:

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的情况下，它如何使用与之类似的功能，但要确保索引在对象上是唯一的.因此，如果您这样做:

So I'm wondering in the case of v8, how it uses a function similar to that but makes sure the index is unique on the object. So if you do this:

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

然后它变成类似:

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

但是如果您在一个对象上具有100或1000或更多的键，则似乎可能会发生碰撞.

But if you have 100's or 1000's or more keys on an object, it seems like there might be collisions.

以v8为例，思考哈希表如何保证其唯一性.

Wondering how a hashtable guarantees they are unique, using v8 as a practical example.

推荐答案

V8开发人员在此处.字符串的哈希值不是唯一的(这就是使用哈希函数的目的)； V8使用二次探测来处理冲突(请参阅> https://en.wikipedia.org/wiki/Hash_table# Collision_resolution .

V8 developer here. Hashes of strings are not unique (that's kind of the point of using a hash function); V8 uses quadratic probing to deal with collisions (see source). You can read more about various strategies at https://en.wikipedia.org/wiki/Hash_table#Collision_resolution.

此外，hash = (hash & hash) % max;太傻了；-)

这篇关于哈希表如何确保对象键被哈希到JavaScript中的唯一索引中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！