Google的稀疏哈希表如何处理冲突? [英] How does google's sparse hash table handle collisions?

问题描述

Google的稀疏哈希表如何处理冲突?即，当2个元素映射到同一存储桶时，它如何确定将新(碰撞)元素放置在何处?我正在阅读稀疏背后的主要实现思想是什么哈希表?，但该答案未涵盖冲突的想法.

How does google's sparse hash table handle collisions? i.e. when 2 elements map to the same bucket, how does it decide where to put the new (colliding) element? I'm reading What is the main implementation idea behind sparse hash table? but that answer doesn't cover the collision idea.

推荐答案

文档此处，具体是:

2c)如果已分配t.sparsetable[i % 32]，但将其赋给foo以外的其他值，请查看t.sparsetable[(i+1) % 32].如果仍然失败，请尝试t.sparsetable[(i+3) % 32]，然后再尝试t.sparsetable[(i+6) % 32].通常，请继续尝试下一个三角数.

2c) If t.sparsetable[i % 32] is assigned, but to a value other than foo, look at t.sparsetable[(i+1) % 32]. If that also fails, try t.sparsetable[(i+3) % 32], then t.sparsetable[(i+6) % 32]. In general, keep trying the next triangular number.

您可以在此处中了解三角数.

You can read about triangular numbers here.

这篇关于Google的稀疏哈希表如何处理冲突?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！