我有一个问题要编码。我有一个生成数字 0 到 n-1 的过程，我想在它生成第一个重复元素时停止它。*我正在寻找一种可以快速完成的数据结构。特别是，添加一个新元素并测试一个元素是否在结构中需要很快。预期的插入数量在 sqrt(n) 左右（生日问题），或者实际上更差一些（比如 sqrt(2n)），因为该过程略微偏向于唯一值。换句话说，它相当稀疏——处理多达 10 亿个数字时，只会使用大约 30 或 50,000 个值。
哈希集或某种自平衡二叉树似乎是正确的方法，但也许有更好的方法？对于小的 n，我认为位数组会更好，但我正在查看 10^9 左右的 n，这对于我认为实用而言太大了。
* 实际上，它不需要立即停止——如果它更有效，您可以在块中生成元素并不时检查。
注意：这最初是在 math.se 上发布的，但他们建议我在这里重新发布。它不是研究级别的，因此不适合 cstheory.se。
哈希表确实是要走的路。一个经过适当优化的整数散列集几乎可以（不能完全忽略负载因子）与普通数组一样节省空间，同时保持您期望的高性能。将键用作哈希值，不要将哈希值存储两次，保持表大小为 2 的幂（因此使用位掩码而不是模数）。如果你使用开放寻址并且需要删除，你可以从 key 中借一点来标记墓碑。
对于 50k 项，这些优化可能不值得编写自己的哈希表（尽管它本身就是一个有趣的练习！）。如果您可以使用您选择的语言中的现有哈希集，请使用它。否则，请参阅Fast and Compact Hash Tables for Integer Keys以了解各种方法的调查和基准，并考虑Robin Hood Hashing这很容易实现，有不错的最坏情况保证，虽然在上述论文中没有提到，但在我的经验中它相当快（主要是因为它是线性探测的简单修改并继承了它的优点）。我的 C 实现——不幸的是还没有公开——甚至没有 250 行代码，包括空格和注释，没有一个是棘手的（与其他哈希表相比）。这没有任何微优化。
我认为最好的数据结构是hashTable。最重要的部分是哈希函数，您可以创建自己的，也可以使用MurmurHash / CityHash进行均匀分布。