Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What kind of hashing function/algorithm does javascript associative array use?

We learned there are many different hashing algorithms/functions, I'm curious which one is used by javascript (v8, if the implementation matters).

like image 292
Novellizator Avatar asked Jun 07 '15 15:06

Novellizator


People also ask

What hash function does JavaScript use?

The hash() function transforms the large keys (strings) into small keys (numbers). It identifies the preferred digit from an array index and converts it into the hash value. The syntax of the hash() function is given as follows. Here, func(string) is a function that takes any input and returns the hash value.

Which algorithm is used for hashing?

Some common hashing algorithms include MD5, SHA-1, SHA-2, NTLM, and LANMAN. MD5: This is the fifth version of the Message Digest algorithm. MD5 creates 128-bit outputs. MD5 was a very commonly used hashing algorithm.

Do JavaScript objects use hashing?

A JavaScript Object is an example of a Hash Table because data is represented a key/value pairs. A hashing function can be used to map the key to an index by taking an input of any size and returning a hash code identifier of a fixed size.

What are the two most common hashing algorithms?

There are many different types of hash algorithms such as RipeMD, Tiger, xxhash and more, but the most common type of hashing used for file integrity checks are MD5, SHA-2 and CRC32. MD5 - An MD5 hash function encodes a string of information and encodes it into a 128-bit fingerprint.


1 Answers

Since V8 is open source, you go to the source:

Here's GetHash(): https://github.com/v8/v8/blob/master/src/objects.cc#L903

And, here's are some of the hash functions for different types: https://github.com/v8/v8-git-mirror/blob/bda7fb22465fc36d99b4053f0ef60cfaa8441209/src/utils.h#L347

And, this looks like the core hash computation for strings: https://code.google.com/p/v8/source/browse/trunk/src/objects.cc?spec=svn6&r=6#3574

uint32_t String::ComputeHashCode(unibrow::CharacterStream* buffer,
                                 int length) {
  // Large string (please note large strings cannot be an array index).
  if (length > kMaxMediumStringSize) return HashField(length, false);

  // Note: the Jenkins one-at-a-time hash function
  uint32_t hash = 0;
  while (buffer->has_more()) {
    uc32 r = buffer->GetNext();
    hash += r;
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);

  // Short string.
  if (length <= kMaxShortStringSize) {
    // Make hash value consistent with value returned from String::Hash.
    buffer->Rewind();
    uint32_t index;
    hash = HashField(hash, ComputeArrayIndex(buffer, &index, length));
    hash = (hash & 0x00FFFFFF) | (length << kShortLengthShift);
    return hash;
  }

  // Medium string (please note medium strings cannot be an array index).
  ASSERT(length <= kMaxMediumStringSize);
  // Make hash value consistent with value returned from String::Hash.
  hash = HashField(hash, false);
  hash = (hash & 0x0000FFFF) | (length << kMediumLengthShift);
  return hash;
}

It's probably worth mentioning that V8 goes to great lengths to avoid using a hash table for object properties whenever possible, preferring to compile known property references into direct index references rather than run-time hash lookups for performance reasons (though this is only possible sometimes - depends upon the code).

like image 63
jfriend00 Avatar answered Sep 19 '22 10:09

jfriend00