Menu
I recently happened to think about object property access times in JavaScript and came across this question which seemed to reasonably suggest that it should be constant time. This also made me wonder if there is a limit on object property key lengths. Apparently modern browsers support key lengths of upto 2^30, which seem to be quite good for a hash function. That said,
Is anyone aware of the kind of hash functions that is used by JS engines?
Is it possible to experimentally create collisions of JavaScript's property accessors?
737
A collision occurs when two keys are hashed to the same index in a hash table. Collisions are a problem because every slot in a hash table is supposed to store a single element.
The maximum number of collisions is equal to the number of items you hash. All items will be hashed to key 3.
You can implement a Hash Table in JavaScript in three steps: Create a HashTable class with table and size initial properties. Add a hash() function to transform keys into indices. Add the set() and get() methods for adding and retrieving key/value pairs from the table.
One method for resolving collisions looks into the hash table and tries to find another open slot to hold the item that caused the collision. A simple way to do this is to start at the original hash value position and then move in a sequential manner through the slots until we encounter the first slot that is empty.
Is anyone aware of the kind of hash functions that is used by JS engines?
Yes, their developers are certainly aware of the hash functions and the problems they have. In fact, attacks based on hash collisions were demonstrated in 2011 against a variety of languages, among others as a DOS attack againt node.js servers.
The v8 team solved the issue, you can read about the details at https://v8project.blogspot.de/2017/08/about-that-hash-flooding-vulnerability.html.
Is it possible to experimentally create collisions of JavaScript's property accessors?
It appears so: https://github.com/hastebrot/V8-Hash-Collision-Generator
73
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
