java - 数据结构 : Which should I use for these conditions?

Question

这应该不是一个困难的问题，但我只是希望在我继续之前有人能回答它。我只需要根据这些预期的 Activity 来决定使用什么数据结构:

1. 需要经常按排序顺序进行迭代(从头开始)。
2. 需要从排序 View 中删除/恢复任意元素。
3. 以后我会经常对数据进行排序并使用多个排序 View 。
4. 稍后我会经常更改元素在其排序 View 中的位置。

顺便说一句，这是用 Java 编写的。

我最好的猜测是，我要么滚动一些自定义链接哈希集(以按排序顺序排列链接)，要么可能只使用树集。但我还不能完全确定。推荐？

编辑:我想由于任意删除/恢复，我应该坚持使用树集，对吧？

其实不一定。嗯……

Answer 1

理论上，我会说正确的数据结构是多路树——最好是 B+ 树之类的东西。传统上这是一种基于磁盘的数据结构，但由于缓存层和虚拟内存，现代主存具有许多相似的特征。

B+ 树的有序迭代非常高效，因为 (1) 您只需遍历叶节点的链表 - 不需要分支节点，并且 (2) 您可以获得非常好的局部性。

与任何平衡树一样，查找、删除和插入任意元素都是 log(n)，尽管具有不同的常数因子。

在树中进行排序主要是选择一种算法，该算法在对 block 的链接列表(叶节点)进行操作时提供良好的性能，最大限度地减少使用叶节点的需要 - 快速排序或合并排序的变体似乎是可能的候选者.一旦项目在分支节点中排序，只需通过叶节点传播回摘要信息。

但是 - 从实用的角度来说，这只是您非常确定自己需要时才会做的事情。很有可能你最好使用一些标准容器。算法/数据结构优化是最好的优化方式，但仍为时过早。