V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
disposablexyz
V2EX  ›  Java

Java data structure O(1) lookup & ordering

  •  
  •   disposablexyz · 2017-02-03 13:51:05 +08:00 via iPhone · 3267 次点击
    这是一个创建于 2850 天前的主题,其中的信息可能已经有所发展或是发生改变。
    Java 有任何 built-in data structure 提供以下特性吗?

    1 ) 查询任何一个 element 的复杂性是 O(1)
    2 )提供有序的 iteration
    28 条回复    2017-02-09 19:48:23 +08:00
    Michaelssss
        1
    Michaelssss  
       2017-02-03 14:08:18 +08:00
    linkedhashmap
    disposablexyz
        2
    disposablexyz  
    OP
       2017-02-03 14:10:28 +08:00
    @Michaelssss  我有想过那个,但是它的 ordering 是根据 insertion order 而不是 comparator 的,所以不算。
    QAPTEAWH
        3
    QAPTEAWH  
       2017-02-03 14:19:35 +08:00 via iPhone
    或者谁证明一下这个是不可能的?
    boywang004
        4
    boywang004  
       2017-02-03 14:20:40 +08:00
    组合一个 TreeMap 和 HashMap 。
    Michaelssss
        5
    Michaelssss  
       2017-02-03 14:21:37 +08:00
    @disposablexyz 那应该没有吧,满足 O ( 1 )这个条件的应该就是 Map 的实现类了,实在不行自己 Override 一下 LinkedHashMap 应该是最快了
    luos543
        6
    luos543  
       2017-02-03 14:22:25 +08:00
    简单来说就是想要 O(n)的有序数据结构?
    allan888
        7
    allan888  
       2017-02-03 14:22:44 +08:00
    红黑树吧。
    TreeMap ,提供有序 order ,但是查询是 log(n), n 不大的情况下 log(n)估计也能接受了。
    otakustay
        8
    otakustay  
       2017-02-03 14:29:36 +08:00
    插入和查询都是 O(1)的使用 comparator 的数据结构不存在的吧……
    只查询 O(1),插入可以 O(n)的话用 2 个结构组合起来就行
    disposablexyz
        9
    disposablexyz  
    OP
       2017-02-03 14:30:31 +08:00
    @QAPTEAWH 是可能的,可以用一个 wrapper 包 HashSet 实现,因为没有其他 operation 的复杂性要求
    @luos543 想要 O(1)的 lookup 的有序数据结构
    @allan888 红黑树不是很 ideal 呢
    disposablexyz
        10
    disposablexyz  
    OP
       2017-02-03 14:31:18 +08:00
    @otakustay 插入不需要 O(1),只有查询需要
    disposablexyz
        11
    disposablexyz  
    OP
       2017-02-03 14:33:19 +08:00
    @otakustay 你的意思是说查询用 HashSet ,插入同时插入到 HastSet 和 TreeSet 么
    disposablexyz
        12
    disposablexyz  
    OP
       2017-02-03 14:34:06 +08:00
    @otakustay 然后 return TreeSet 的 iterator ?
    disposablexyz
        13
    disposablexyz  
    OP
       2017-02-03 14:34:54 +08:00
    ehhh, by set I mean map
    otakustay
        14
    otakustay  
       2017-02-03 14:36:28 +08:00
    @disposablexyz yes ,内存应该够的吧
    disposablexyz
        15
    disposablexyz  
    OP
       2017-02-03 14:40:37 +08:00
    @otakustay 不大好
    otakustay
        16
    otakustay  
       2017-02-03 14:40:57 +08:00
    @disposablexyz 你都不说不好在哪里……
    luos543
        17
    luos543  
       2017-02-03 14:41:55 +08:00
    感觉这样的数据结构挺小众的。创建 iteration 的时候才做 sorting ,不会对机器很大负担么?
    disposablexyz
        18
    disposablexyz  
    OP
       2017-02-03 14:47:14 +08:00
    @luos543 创建 iteration 的时候才做 sorting 是我能想出来的解决方案,但不一定是这样,也可以在 insert 的时候做。实际上我不需要知道怎么做到,只要求能够有一个 sorted 的 iteration 和 O(1)的查询
    allan888
        19
    allan888  
       2017-02-03 14:54:45 +08:00
    你仅仅是查询加有序遍历,明显 hashmap+treemap 是可以的。
    可以做到插入 O(logn), 删除 O(logn), 查询 O(1), 修改 O(logn), 也能有序遍历。
    bumz
        20
    bumz  
       2017-02-03 15:53:26 +08:00
    1) 查询任何一个 element 的复杂性是 O(1) —— HashMap
    2) 提供有序的 iteration —— TreeMap

    一个新的数据结构诞生了:"IterableHashMap",用 HashMap 做查询, TreeMap 提供迭代器。
    clarkok
        21
    clarkok  
       2017-02-03 16:48:41 +08:00 via Android
    提供一个思路,用 hash func 是 X % N 的 hash 表?并且冲突的用链表从大到小链起来
    clarkok
        22
    clarkok  
       2017-02-03 16:49:32 +08:00 via Android
    @clarkok 从大到小 → 从小到大
    shyling
        23
    shyling  
       2017-02-03 17:16:43 +08:00
    选择一个合适的 hash 算法
    SuperFashi
        24
    SuperFashi  
       2017-02-03 21:00:05 +08:00
    @allan888 @bumz 正解
    你说的数据结构目前是没有的,只能搞两棵树分别提供不同的功能。
    breeswish
        25
    breeswish  
       2017-02-04 10:00:02 +08:00
    确保 obj1 <= obj2 时 hash(obj1) <= hash(obj2),这样大概就可以有序地 iterate 了
    bumz
        26
    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
        27
    srlp  
       2017-02-05 10:54:20 +08:00
    所以答案很明显了,就是没有。楼主要自己实现一个。

    @otakustay 猜测,楼主说不好,是要保存两个 value 的“值”在树里面... 不过反正我觉得这也没什么好的办法。
    @breeswish 这也不能保证, hash 之后要取模的。
    KentY
        28
    KentY  
       2017-02-09 19:48:23 +08:00
    我觉得 OP 没有描述清楚. 按照我的理解:

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

    换句话说,你可以用最慢的排序方法, 哪怕是 O(n^n)的, 也与你要求的数据结构没关系, 你只要求了提取数据 O(1), 并且可以按照排好序的方式 iteration.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1359 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 17:36 · PVG 01:36 · LAX 09:36 · JFK 12:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.