具有O（1）插入和O（log（n））搜索复杂性的数据结构？

Question

有没有可用的数据结构，即使在最坏的情况下也可以提供O（1）（即常量）插入复杂度和O（log（n））搜索复杂度？

排序的向量可以执行O（log（n））搜索，但是插入将花费O（n）（这是因为我并不总是在元素的前面或后面插入元素）。列表可以进行O（1）插入，但不能提供O（log（n））查找。

我不知道这样的数据结构是否可以实现。

Answer 1

我想知道这样的数据结构是否可以实现。

恐怕答案是否定的。

搜索可以，插入不行

当我们观察二叉搜索树、B 树、红黑树和 AVL 树等数据结构时，它们的平均搜索复杂度为O(log N)，但同时平均插入复杂度也为O(log N)。原因很明显，搜索将遵循（或浏览）插入发生的相同模式。

插入可以，搜索不行

像单链表、双向链表这样的数据结构的平均插入复杂度为O(1)，但是单链表和双链表中的搜索同样很痛苦O(N)，因为它们没有任何基于索引的元素访问支持。

你的问题的答案在于Skiplist实现，它是一个链接列表，但仍然需要O(log N)平均插入（当列表预计在 中插入时O(1)）。

最后要说的是，Hashmap 非常接近于满足快速搜索和快速插入的要求，但代价是巨大的空间，但如果实现得很糟糕，它可能会导致O(N)插入和搜索的复杂性。