对于有插入（范围插入）、 删除（范围删除）、 下标获取要求性能最好的数据结构是什么？

[wdc63]

现在开发的项目对性能比较敏感，有一个列表结构频繁地会通过索引获取对象，通过下标或对象本身删除列表中的一个或多个对象，在列表中间某个位置、尾部插入一个或多个对象，请问能不能实现这种数据结构让每种方法都以 O(1)的方式进行。

[THESDZ]

通过下标获取的，是数组吧？（这个问题应该是这么简单吧？）

[wdc63]

@THESDZ 数组下标获取是 O1 ，但 InsertAt 、RemoveAt 、Remove(obj)都有 O(n)的时间开销，希望能后面几种方法也能以 O1 实现。

[MoYi123]

#include <ext/pb_ds/assoc_container.hpp>

只能 O(logn),而且常数不小.

[xtreme1]

at() 和 removeAt() 应该没法同时 O(1)吧..

[cogear]

以我的见识来说，查询和插入都做到 O1 是不可能的。

线性表（数组）查询可以 O1 。
链表插入删除可以 O1 ，但是查询是 O(n)

跳跃表？能在插入和查询之间做个平衡，O(logN)，但是不能 O1 。

[wdc63]

@MoYi123 能否解释一下这种算法，只会 C#、JAVA 和 Python ，C++看起来太费劲。

[wdc63]

@cogear 能否做到查询 O1 ，插入 Ologn 。

[dcsuibian]

哈希表，平均 O(1)，最差 O(n)。。。

[wdc63]

@dcsuibian hash 表没法用下标查询。

[Jooooooooo]

一个简单的思路出发点是用空间去换时间

比如你维护多份相同的数据

[wdc63]

@Jooooooooo 具体怎样能实现呢？

[Jooooooooo]

@wdc63 简单想了一下, 先用 linkedList, 这样范围的插入和删除就是 O(1) 的

接下来问题是怎么找到 list 里对应的节点, 再用一个 map, 维护所有数据在上面 list 里的 index, 这样来了一个元素要查找能立马得知它在 list 哪个位置 (object -> index)

接下来再有一个问题是, 怎么快速遍历到 list 对应的位置上, 再用一个 map, 记录所有 index 指向的节点, 比如第 0 个元素的指针, 第 1 个元素的指针

这样有可能可以?? 不过细节得再想想. (在不考虑并发的前提下

[Jooooooooo]

@Jooooooooo 噢不行, index 没法维护...得再想想别的方案了.

[thinkershare]

@wdc63 没有这种数据结构, 不用找了

[cogear]

@wdc63 不能，查询做不到 O1 ，查询大约是二分查找的性能

[MoYi123]

@wdc63 有点问题, 这个不是很合适.

[jhdxr]

『通过索引获取对象，通过下标』
如果你觉得索引和下标是不一样的。那你不是默认就只剩数组了，链表之类的哪来下标？

[seers]

哈西链表

[MoYi123]

@wdc63


看下这个库吧, from sortedcontainers import SortedList
把注释删掉大约 600 行

但是中间插入不好搞. 必须定期重新构建整个数据结构.

from sortedcontainers import SortedList

a = [0]


def incr():
a[0] += 1
return a[0]


s = SortedList()
invert = {}
# 向尾部插入单个
idx = incr()
s.add([idx, 'A'])
invert['A'] = idx

idx = incr()
s.add([idx, 'B'])
invert['B'] = idx

# 用下标获取
print(s[0]) # [1, 'A']
print(s[1]) # [2, 'B']

# 用下标删除
s.pop(0)
print(s)

# 用对象本身删除
idx = invert['B']
idx = s.bisect_left([idx, 'B'])
s.pop(idx)

print(s)

# 中间插入(先插入 2 个值)
idx = incr()
s.add([idx, 'A'])
invert['A'] = idx

idx = incr()
s.add([idx, 'B'])
invert['B'] = idx

# 中间插入,在 A,B 间加一个 C
# 这里比较尴尬, float 精度有限, 需要定期用 O(n)重新构建整个表
left = s[0][0]
right = s[1][0]
s.add([(left + right) / 2, 'C'])
print(s)

[sunny352787]

不是，等一下，不会又碰到了 AB 问题了吧？为啥一定要用下标呢？一般来说 hash 表就可以了啊，你这是个什么场景一定要用数组下标这种形式呢？

[aguesuka]

这段代码能 O(1) 地 [添加元素返回下标] , [通过下标获得元素], [通过下标删除元素].
但是列表是无序的, 不能保证删除的幂等性.

https://github.com/aguesuka/torrent-finder/blob/dev-nio2/src/main/java/cc/aguesuka/maguet/util/ArrayHeapSpace.java

[RicardoY]

块状链表这个场景应该蛮快的，如果数据量不是太大的话，复杂度比你要求的高一点

[hsfzxjy]

了解下跳表 skip list

[joetse]

只有完美哈希可以做到，前提是无限内存

[dqzcwxb]

世间安得双全法

[AllenHua]

优先保证插入和删除是 o(1) 应该就是链表为主的结构了，但又要保证查询是 o(1) 应该是做不到的，在查询上妥协一些应该是比较理想的方案

[qbqbqbqb]

所有方法都 O(1)是不行的
可以做到所有方法都是 O(log n)

主要有两大类：
* 跳跃表（ skip list ），单次操作时间复杂度为期望 O(log n)，实现较为简单
* 带有 order statistics 的平衡二叉搜索树（包括 AVL, 红黑树, Splay 等多种实现），根据实现的不同，单次操作时间复杂度为期望、均摊或严格 O(log n)，实现较为复杂

[wdc63]

@qbqbqbqb
@AllenHua
@aguesuka
@MoYi123
感谢，已经放弃用下标取得对象的方法了，用下标的方法主要是为了方便前台用户交互部分获取数据的逻辑，现在就用 hashset ，改写了前台的逻辑，直接获取到对象而不是下标，再在逻辑部分进行处理。