v8 如何对散列中的键进行散列 table

Question

在学习时，我想知道 v8 用于从键创建哈希的算法，以及它们用作键的内容（对于字符串键）。哈希 table 密钥生成的大多数示例都是 hello world 示例，并且容易受到碰撞攻击和其他问题。我正在寻找生产系统如何实现哈希 table 的示例，例如 v8.

浏览 v8 source 很有帮助，但有点难以理解。

Answer 1

V8的字符串哈希实现在src/string-hasher-inl.h中，它的核心部分是下面的函数，"adds"一个新的字符到"running hash"，循环调用对于字符串中的每个字符：

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

根据定义，每个散列 table 都可能发生冲突。碰撞攻击是否是一个问题取决于应用程序（例如，处理客户端输入的服务器可能想要防止基于碰撞的 DoS 攻击；而 Web 浏览器通常不需要关心：如果客户端脚本想要创建无用的 CPU 加载，它可以简单地执行 for (;;) {} -- 但为什么任何脚本都想要这样做？）。

一种可能的抵御碰撞攻击的方法是用一个随机值（例如在应用程序启动时选择）而不是 0 来初始化（"salt"）每个字符串的 "running hash"。这样攻击者就无法预测哪个字符串可能有冲突的哈希值。

v8 如何对散列中的键进行散列 table

How v8 hashes the keys in a hash table

javascript

hash

v8

hashtable

data-structures