Java data structure O(1) lookup & ordering

2017-02-03 13:51:05 +08:00
 disposablexyz
Java 有任何 built-in data structure 提供以下特性吗?

1 ) 查询任何一个 element 的复杂性是 O(1)
2 )提供有序的 iteration
3384 次点击
所在节点    Java
28 条回复
clarkok
2017-02-03 16:48:41 +08:00
提供一个思路,用 hash func 是 X % N 的 hash 表?并且冲突的用链表从大到小链起来
clarkok
2017-02-03 16:49:32 +08:00
@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.

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/337863

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX