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

[wdc63]

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

[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 ，改写了前台的逻辑，直接获取到对象而不是下标，再在逻辑部分进行处理。