Java data structure O(1) lookup & ordering

[disposablexyz]

Java 有任何 built-in data structure 提供以下特性吗？

1 ） 查询任何一个 element 的复杂性是 O(1)
2 ）提供有序的 iteration

[Michaelssss]

linkedhashmap

[disposablexyz]

@Michaelssss  我有想过那个，但是它的 ordering 是根据 insertion order 而不是 comparator 的，所以不算。

[QAPTEAWH]

或者谁证明一下这个是不可能的？

[boywang004]

组合一个 TreeMap 和 HashMap 。

[Michaelssss]

@disposablexyz 那应该没有吧，满足 O （ 1 ）这个条件的应该就是 Map 的实现类了，实在不行自己 Override 一下 LinkedHashMap 应该是最快了

[luos543]

简单来说就是想要 O(n)的有序数据结构?

[allan888]

红黑树吧。
TreeMap ，提供有序 order ，但是查询是 log(n)， n 不大的情况下 log(n)估计也能接受了。

[otakustay]

插入和查询都是 O(1)的使用 comparator 的数据结构不存在的吧……
只查询 O(1)，插入可以 O(n)的话用 2 个结构组合起来就行

[disposablexyz]

@QAPTEAWH 是可能的，可以用一个 wrapper 包 HashSet 实现，因为没有其他 operation 的复杂性要求
@luos543 想要 O(1)的 lookup 的有序数据结构
@allan888 红黑树不是很 ideal 呢

[disposablexyz]

@otakustay 插入不需要 O(1)，只有查询需要

[disposablexyz]

@otakustay 你的意思是说查询用 HashSet ，插入同时插入到 HastSet 和 TreeSet 么

[disposablexyz]

@otakustay 然后 return TreeSet 的 iterator ？

[disposablexyz]

ehhh, by set I mean map

[otakustay]

@disposablexyz yes ，内存应该够的吧

[disposablexyz]

@otakustay 不大好

[otakustay]

@disposablexyz 你都不说不好在哪里……

[luos543]

感觉这样的数据结构挺小众的。创建 iteration 的时候才做 sorting ，不会对机器很大负担么？

[disposablexyz]

@luos543 创建 iteration 的时候才做 sorting 是我能想出来的解决方案，但不一定是这样，也可以在 insert 的时候做。实际上我不需要知道怎么做到，只要求能够有一个 sorted 的 iteration 和 O(1)的查询

[allan888]

你仅仅是查询加有序遍历，明显 hashmap+treemap 是可以的。
可以做到插入 O(logn), 删除 O(logn), 查询 O(1), 修改 O(logn), 也能有序遍历。

[bumz]

1) 查询任何一个 element 的复杂性是 O(1) —— HashMap
2) 提供有序的 iteration —— TreeMap

一个新的数据结构诞生了："IterableHashMap"，用 HashMap 做查询， TreeMap 提供迭代器。