我想知道是否有一种简单的数据结构支持平摊log(n)查找和插入，就像自平衡二叉搜索树一样，但内存开销恒定。(我真的不关心删除元素)。
我的一个想法是把所有的东西都存储在一个连续的内存块中，这个内存块分为两个连续的块:一个是所有元素都排序的S部分，一个是没有排序的U部分。
要执行插入操作，我们可以向U中添加一个元素，如果U的大小超过log(S的大小)，则对整个连续数组进行排序(将S和U视为一个连续数组)，因此排序后所有元素都在S中，U为空。
要执行查找，在S上运行二进制搜索，并且只查找所有u
然而，我在计算我的算法的平摊插入时间时遇到了麻烦。
最终，我只希望有一些合理简单的算法/数据结构，具有理想的属性，并保证它在平摊时间内运行得相当快。
谢谢!
如果通过常量内存开销，您的意思是存储在数据结构中的N元素的空间消耗应该是O(N)，那么任何平衡树都可以——实际上，任何n -ary树都将元素存储在外部叶子中，其中n > 1和每个外部树都包含一个元素，具有此属性。
这是因为任何有N个节点的树图都有N - 1条边。
如果你所说的常量内存开销是指对于N元素的空间消耗应该是N + O(1)，那么平衡树和哈希表都没有这个属性——它们都将使用k * N内存，其中k > 1是由于树的情况下额外的节点指针和哈希表的情况下的负载因子。
我觉得你的方法很有趣，但我不认为它会工作，即使你只排序U，然后合并两个集合在线性时间。您需要在每次logN更新之后进行排序(O(logN * log(logN))操作)，然后在O(n)中合并S和U(注意，到目前为止，没有人真正知道如何在线性时间内完成此操作，也就是说，没有额外的数组)。
平摊插入时间为O(n / logN)。但如果你允许U的大小增长到s的平方根，你可以使用你的方法来实现接近O(√n)的结果
任何哈希表都可以这样做。唯一棘手的部分是如何解决冲突-有几种方法可以做到这一点，另一个棘手的部分是正确的哈希计算。
看:http://en.wikipedia.org/wiki/Hash_table