JavaScript关联数组使用哪种哈希函数/算法？

Question

我们了解到有许多不同的哈希算法/函数，我很好奇 JavaScript（v8，如果实现有关系的话）使用哪一个。

- Novellizator

---

我认为你最好向js v8开发人员提出问题 https://code.google.com/p/v8/ - oscargilfc

不确定它是否与实现相关。 - Novellizator

我也不确定，但如果它不是特定于实现的，我相信他们知道。 - oscargilfc

Answer 1

由于V8是开源的，您可以查看源代码：

这里是GetHash(): https://github.com/v8/v8/blob/master/src/objects.cc#L903

这里是不同类型的哈希函数：https://github.com/v8/v8-git-mirror/blob/bda7fb22465fc36d99b4053f0ef60cfaa8441209/src/utils.h#L347

而且，这似乎是字符串的核心哈希计算：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;
}

值得一提的是，V8会尽可能避免使用哈希表来存储对象属性，而是将已知的属性引用编译成直接的索引引用，以避免运行时哈希查找的开销（尽管有时这种优化是不可能的-取决于代码）。

- jfriend00

---

V8引擎如何处理哈希冲突？它采用了哪种技术？https://en.wikipedia.org/wiki/Hash_table#Collision_resolution - Novellizator