Java data structure O(1) lookup & ordering

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2851 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

28 条回复 • 2017-02-09 19:48:23 +08:00

Michaelssss

2017-02-03 14:08:18 +08:00

linkedhashmap

disposablexyz

2017-02-03 14:10:28 +08:00

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

QAPTEAWH

2017-02-03 14:19:35 +08:00 via iPhone

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

boywang004

2017-02-03 14:20:40 +08:00

组合一个 TreeMap 和 HashMap 。

Michaelssss

2017-02-03 14:21:37 +08:00

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

luos543

2017-02-03 14:22:25 +08:00

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

allan888

2017-02-03 14:22:44 +08:00

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

otakustay

2017-02-03 14:29:36 +08:00

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

disposablexyz

2017-02-03 14:30:31 +08:00

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

disposablexyz

2017-02-03 14:31:18 +08:00

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

disposablexyz

2017-02-03 14:33:19 +08:00

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

disposablexyz

2017-02-03 14:34:06 +08:00

@otakustay 然后 return TreeSet 的 iterator ？

disposablexyz

2017-02-03 14:34:54 +08:00

ehhh, by set I mean map

otakustay

2017-02-03 14:36:28 +08:00

@disposablexyz yes ，内存应该够的吧

disposablexyz

2017-02-03 14:40:37 +08:00

@otakustay 不大好

otakustay

2017-02-03 14:40:57 +08:00

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

luos543

2017-02-03 14:41:55 +08:00

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

disposablexyz

2017-02-03 14:47:14 +08:00

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

allan888

2017-02-03 14:54:45 +08:00

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

bumz

2017-02-03 15:53:26 +08:00

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

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

clarkok

2017-02-03 16:48:41 +08:00 via Android

提供一个思路，用 hash func 是 X % N 的 hash 表？并且冲突的用链表从大到小链起来

clarkok

2017-02-03 16:49:32 +08:00 via Android

@clarkok 从大到小 → 从小到大

shyling

2017-02-03 17:16:43 +08:00

选择一个合适的 hash 算法

SuperFashi

2017-02-03 21:00:05 +08:00

@allan888 @bumz 正解
你说的数据结构目前是没有的，只能搞两棵树分别提供不同的功能。

breeswish

2017-02-04 10:00:02 +08:00

确保 obj1 <= obj2 时 hash(obj1) <= hash(obj2)，这样大概就可以有序地 iterate 了

bumz

2017-02-04 11:48:50 +08:00

其实 n 很小的时候 O(log(n)) 往往比 O(1) 更快，因为
O(1) 算法前面的常数往往很大，比如 hash 算法
HashMap 是为数据量很大且相互没有什么简单联系的数据准备的。

如果数据量大到连 O(log(n)) 的算法都不够用，那恐怕此时按顺序迭代也没有什么意义了，给你几台超级计算机，从宇宙诞生开始算，算到现在都不见得算得完。

综上，如果按顺序迭代还有意义，那么何不直接利用这一顺序建立数据结构—— TreeMap 呢？此时的 O(log(n)) 完全可以看成 O(1)。

srlp

2017-02-05 10:54:20 +08:00

所以答案很明显了，就是没有。楼主要自己实现一个。

@otakustay 猜测，楼主说不好，是要保存两个 value 的“值”在树里面... 不过反正我觉得这也没什么好的办法。
@breeswish 这也不能保证， hash 之后要取模的。

KentY

2017-02-09 19:48:23 +08:00

我觉得 OP 没有描述清楚. 按照我的理解:

如果只关注查询的复杂度, 不管插入的复杂度, 就可以不关心有排序与否, 你完全可以用一个 linkedhashmap, 然后插入你已经排序好的数据, 或者 treemap 也可以, 方便点.

换句话说,你可以用最慢的排序方法, 哪怕是 O(n^n)的, 也与你要求的数据结构没关系, 你只要求了提取数据 O(1), 并且可以按照排好序的方式 iteration.