1

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.

Lance
  • 75,200
  • 93
  • 289
  • 503
  • 1
    https://stackoverflow.com/questions/9282869/are-there-limits-to-the-number-of-properties-in-a-javascript-object – Lance Dec 31 '17 at 22:39
  • No, any hashtable implementation needs some way to handle collisions. If hashes were guaranteed to be unique, they would not have any size benefit. – Bergi Dec 31 '17 at 22:41
  • You cannot predict the size of a string set, hence there will be collisions at some point. However, collisions can be handled with collections as simple as queues. – Frederik.L Dec 31 '17 at 22:50
  • Looking to know how to do that, that sounds like a good solution. – Lance Dec 31 '17 at 22:58
  • @Bergi: Actually there is such a thing as a [perfect hash](https://en.m.wikipedia.org/wiki/Perfect_hash_function), which has no collisions and no wasted space, but it's not applicable in this case. – psmears Dec 31 '17 at 23:14

1 Answers1

3

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 ;-)

jmrk
  • 34,271
  • 7
  • 59
  • 74