hashtable - google 的稀疏哈希表如何处理冲突？

Question

google 的稀疏哈希表如何处理冲突？即，当 2 个元素映射到同一个桶时，它如何决定将新（碰撞）元素放在哪里？我正在阅读稀疏哈希表背后的主要实现思想是什么？但该答案并未涵盖碰撞的想法。

Answer 1

您的问题已在此处的文档中得到解答，特别是：

2c) 如果t.sparsetable[i % 32]已赋值，但赋值为 foo 以外的值，请查看t.sparsetable[(i+1) % 32]. 如果这也失败，请尝试t.sparsetable[(i+3) % 32]，然后t.sparsetable[(i+6) % 32]。一般来说，继续尝试下一个三角形数。

您可以在此处阅读有关三角数的信息。