CODEWITHSUNDEEP
javascriptdata-structureshashhashtablev8
Lance Pollard
Lance Pollard

Reputation: 79358

How v8 hashes the keys in a hash table

In learning how to implement a robust hash table, I am wondering the algorithm v8 uses to create the hash from a key, and what they use as the key (for string keys). Most of the examples on hash table key generation are hello world examples and subject to collision attacks and other things. I am looking for an example of how a production system implements a hash table, such as v8.

Looking through the v8 source has been helpful, but it is a bit over my head.

Upvotes: 0

Views: 818

Answers (1)

jmrk
jmrk

Reputation: 40561

V8's string hashing implementation is in src/string-hasher-inl.h, its core part is the following function, which "adds" a new character to the "running hash", and is invoked in a loop for every character in the string:

uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
  running_hash += c;
  running_hash += (running_hash << 10);
  running_hash ^= (running_hash >> 6);
  return running_hash;
}

By definition, every hash table can have collisions. Whether collision attacks are a concern depends on the application (for example, a server processing client input might want to guard against collision-based DoS attacks; whereas a web browser typically doesn't need to care: if client-side script wanted to create useless CPU load, it could simply do for (;;) {} -- but why would any script want to do that?).

A possible defense against collision attacks is to initialize ("salt") every string's "running hash" with a random value (that's e.g. chosen at application startup) instead of 0. That way attackers cannot predict which strings might have colliding hashes.

Upvotes: 3

Related Questions