CODEWITHSUNDEEP
javascripthashtableunique
Lance Pollard
Lance Pollard

Reputation: 79358

How hashtable makes sure object keys are hashed into a unique index in 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;
}

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' }

Then it becomes something like:

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

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

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

Upvotes: 1

Views: 306

Answers (1)

jmrk
jmrk

Reputation: 40561

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.

Also, hash = (hash & hash) % max; is pretty silly ;-)

Upvotes: 3

Related Questions