我知道如果我有均匀分布的整数键或可以映射到均匀分布的整数的键，我可以简单地将桶数组用于关联容器。如果我可以创建足够大的数组以确保某个负载因子（假设集合不是太动态），那么键的预期冲突次数将是有限的，因为这只是具有身份哈希函数的哈希表。
编辑：我认为字符串等同于 [0..1] 范围内的位置分数。因此，它们可以通过乘法和取结果映射到任何整数范围。
我也可以有效地进行前缀查询，就像尝试一样。我假设（不知道证明）与给定前缀相对应的空槽的预期数量必须在到达具有至少一个元素的第一个桶之前按顺序跳过也将受到常数的限制（再次取决于选择的负载系数）。
当然，我可以在最坏情况下的常数时间内进行 stabbing 查询，并在仅输出敏感的线性预期时间的范围内查询（如果上一段中的密集猜想确实是真的）。
那么尝试的好处是什么？
如果分布是均匀的，我看不到任何尝试做得更好的东西。但我可能错了。
如果分布具有较大的未补偿偏斜（因为我们没有先验概率或仅查看最坏情况），则桶数组的性能很差，但尝试也会变得严重不平衡，并且可以在任意长度的字符串中具有线性的最坏情况性能。因此，对您的数据使用任何一种结构都是值得怀疑的。
所以我的问题是 -在可以正式证明的桶数组上尝试的性能优势是什么？什么样的分布会带来这些优势？
我正在考虑在不同尺度上具有自相似结构的分布。我相信那些被称为分形分布，我承认对此一无所知。可能是这样，如果分布倾向于在每个规模上聚集，尝试可以提供卓越的性能，通过保持每个节点的负载因子相似，根据需要在密集区域添加级别 - 这是桶阵列无法做到的。
谢谢