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