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

Java ArrayList 不服来辩

  •  
  •   guguji · 215 天前 · 5386 次点击
    这是一个创建于 215 天前的主题,其中的信息可能已经有所发展或是发生改变。

    get(int index) 方法时间复杂度 O(1),如何做的到? - 如果底层是基于数组,那么数组为什么可以根据索引快速访问到数据?

    remove(int index) 方法时间复杂度 O(N2) - 如果有大批量的数据在 list 中,且要删除其中一个元素,请问如何优化? - 就基于 ArrayList 来做,不该变成 LinkedList 这种?

    第 1 条附言  ·  187 天前
    嗐,理解偏差,我也不是闲人,标题确实有引战嫌疑。。。道歉
    增加下场景大家明白了,没必要这样~

    这个两个问题其实是某个面试官的问题,我觉得很清奇
    我详细明确下前因后果:

    1.get 问题
    问:get 为何能快速找到
    答:连续内存地址,a[i] = arr 起始地址 + 数组元素大小累加
    问:知道地址就能找到?操作系统了解么
    答:。。。

    第一个问题我没想到会问到操作系统层面,感觉没必要,可能想要一杆子打到底。。。

    2. remove
    问:为何删除会慢
    答:删除会挪动数组,效率差
    问:有啥优化办法?
    答:可以使用 linkedlist ,不过 get 会耗时,如果要达到 o(1)的话,可以 hash+linkedlist 。
    问:假设就基于 arraylist 接口,且数据量很大,如何提升删除效率
    答:。。。


    关于问题 2 ,我觉得可以参考 hashmap 的原理来实现,数组内存储的不是元素,而是链表 or 红黑树。
    没啥其他的想法,。。

    如果限定条件是只能用 arraylist ,如何来提升 remove 的效率呢?大牛们可以 show 了~
    67 条回复    2023-12-21 10:08:57 +08:00
    Masoud2023
        1
    Masoud2023  
       215 天前   ❤️ 64
    你这个问题应该回学校好好学学数据结构,而不是在这不服来辩
    thevita
        2
    thevita  
       215 天前   ❤️ 1
    要辩你应该先陈述自己的观点,不应该是问句

    ps:
    remove(int index) 复杂度 O(N2) 写错了吧。remove(Object o) 才是 O(N^2)
    me1onsoda
        3
    me1onsoda  
       215 天前   ❤️ 2
    那么数组为什么可以根据索引快速访问到数据?

    大哥,数组存的数据在内存是连续的,当然可以根据索引来快速检索
    thevita
        4
    thevita  
       215 天前
    @thevita 屑,说错了,忽略我
    emSaVya
        5
    emSaVya  
       215 天前   ❤️ 16
    这位更是重量级。
    gangoogle
        6
    gangoogle  
       215 天前   ❤️ 1
    数组在内存里面 第一个位置 0x0 第二个 0x2 我想取第 10 个元素直接 0x0+9 不就直接拿到了吗。。。。
    xaplux
        7
    xaplux  
       215 天前
    额,哪来的勇气啊,数组存储是连续的
    get 根据下标直接可以寻址了
    remove 时间复杂度是 O(n) ,主要是删除一个元素后,其之后的元素要移动啊,如果删除的是最好一个元素,复杂度可以做到 O(1)
    a0210077
        8
    a0210077  
       215 天前
    服,请参考数据结构的数组章节
    xaplux
        9
    xaplux  
       215 天前
    ArrayList 和 LinkedList 的使用场景是不一样的,鱼和熊掌不可兼得,所以要权衡
    如果需要频繁删除,那用 LinkedList 相对 ArrayList 要合适
    fresco
        10
    fresco  
       215 天前
    这不是大学的内容么
    PVXLL
        11
    PVXLL  
       215 天前   ❤️ 1
    震惊~
    quicksand
        12
    quicksand  
       215 天前
    @xaplux 如果对顺序无要求,可以通过将最后一个元素移动到被删除的元素来把复杂度降到 O(1)
    Ayanokouji
        13
    Ayanokouji  
       215 天前
    不会的话,虚心请教不行吗,非要起这么一个标题找喷
    hidemyself
        14
    hidemyself  
       215 天前
    我怀疑你是来钓鱼的。
    xaplux
        15
    xaplux  
       215 天前
    @quicksand 是的,看情况没少刷题
    Deeymmm
        16
    Deeymmm  
       215 天前
    挺好,又 block 一个人
    xtreme1
        17
    xtreme1  
       215 天前
    钓的是_, 没的是_
    swczxf
        18
    swczxf  
       215 天前 via iPhone
    这是不是叫民科
    Jrue0011
        19
    Jrue0011  
       215 天前
    额,看历史发帖和回复也不应该啊
    mdn
        20
    mdn  
       215 天前
    不服来辩 === 求求大家告诉我答案
    deplivesb
        21
    deplivesb  
       215 天前
    op 的 blog 和他的三个帖子,看出来就是个 xx
    Ericcccccccc
        22
    Ericcccccccc  
       215 天前
    重新学下组成原理?
    issakchill
        23
    issakchill  
       215 天前
    为啥不问问神奇的 chatgpt?
    coderxy
        24
    coderxy  
       215 天前
    我原来面试别人的时候,不少人分不清数组跟链表的区别的时候我的心理活动跟现在一模一样的
    oneisall8955
        25
    oneisall8955  
       215 天前 via Android
    钓鱼贴
    maxssy
        26
    maxssy  
       215 天前   ❤️ 1
    1. ArrayList 的首个元素的地址是已知的
    2. ArrayList 底层实现在内存上表现为各个元素顺序排放的数组
    3. ArrayList 每个元素的内存占用大小是已知的
    所以
    get 在取得索引后可以通过公式: `目标元素的地址 = 首元素地址 + 索引 * 每个元素的内存占用大小` 来取得, 所以时间复杂度是 O(1)

    又因为各元素是顺序排放的, remove 某个元素后需要重新排列整个数组, 所以是 O(n)
    cyndihuifei
        27
    cyndihuifei  
       215 天前
    为什么这种问题都搞不清楚还要发技术文章
    dragondove
        28
    dragondove  
       215 天前   ❤️ 3
    @xaplux 实际上 LinkedList 已经基本没有适合使用的地方了,具体可以看这个知乎回答 https://www.zhihu.com/question/563680801/answer/2750393567
    zengmingyang96
        29
    zengmingyang96  
       215 天前
    数组为什么可以根据索引快速访问到数据? 因为内存支持随机读取 😂
    v2eb
        30
    v2eb  
       215 天前
    @coderxy 真有这种人嘛😂
    neptuno
        31
    neptuno  
       215 天前 via iPhone
    我一般都是钻到内存里面,自己去找地址
    BeautifulSoap
        32
    BeautifulSoap  
       215 天前 via Android
    本来以为 lz 想要问的是内存电路是怎么寻址的,实但仔细想想 lz 可能真的连数组是啥都不懂。。。
    oneisall8955
        33
    oneisall8955  
       215 天前
    @dragondove 偶尔还是会用到的,不确定数量情况下
    dk7952638
        34
    dk7952638  
       215 天前
    看这标题,以为来到了贴吧
    xiangbohua
        35
    xiangbohua  
       215 天前
    你说了几个问题,你都没给结论,辩论啥
    haolongsun
        36
    haolongsun  
       215 天前
    没上过数据结构?底层是数组,再细说是对数组首地址的引用,快速访问到素就是首地址+偏移量*数组元素 sizeof,这就是 O(1),再多说就是 arraylist 的结构就是一个指向堆上数组的指针,一个 len ,一个 cap 。
    BanGanExpert
        37
    BanGanExpert  
       215 天前
    @v2eb 以前本身业务需求多,JavaWeb 上手不又难,造成很多基础不扎实,不清楚基本的数据结构知识,很多人也能进入行业做开发。当然现在新人水平普遍是专业对口毕业的,自然很大程度上都没这个情况了。我以前面试人一般第一个问题就是,你写 Java 用了哪些线性结构的集合实现,分别在哪种场景,除了当普通集合还能干嘛( Stack 、Heap 、Queue )。
    xhinliang
        38
    xhinliang  
       215 天前
    挺好,又 block 一个人
    strrng
        39
    strrng  
       215 天前
    OP 感觉多少是有点搞笑了😄
    zcm3579
        40
    zcm3579  
       215 天前
    辩了个勾巴 , 脑残就不要发帖
    Cooky
        41
    Cooky  
       215 天前
    看来裁员裁的还不够多
    makelove
        42
    makelove  
       215 天前
    你不适合这个职业,趁早转行
    zhch602
        43
    zhch602  
       215 天前 via iPhone
    这时候就看出来第一门语言学 C 的好处了——不会问出这种弱智问题
    Yadomin
        44
    Yadomin  
       215 天前 via Android
    可见科班出身的必要性
    idealhs
        45
    idealhs  
       215 天前   ❤️ 1
    跟个弱智一样
    IvanLi127
        46
    IvanLi127  
       215 天前 via Android
    什么鬼。。。这问题能问得出口?这属于话不会说,代码也不懂写。
    Qzier
        47
    Qzier  
       215 天前 via iPhone
    培训班出来的?没学过数据结构吗?
    NoKey
        48
    NoKey  
       215 天前
    为啥不问问神奇的 chatgpt?
    learningman
        49
    learningman  
       215 天前 via Android
    搞 Java 搞的
    kachu673
        50
    kachu673  
       215 天前
    原来真有程序员不懂这些东西。。。可见科班的重要性了
    4kingRAS
        51
    4kingRAS  
       215 天前
    类似你找车位,数组就是车位有刷编号,那不就 O (1) 找到了吗
    kylix
        52
    kylix  
       215 天前
    OP 抛了问题后,匿了
    czzhengkw
        53
    czzhengkw  
       214 天前
    https://jifuwei.github.io/

    大家去 OP 的博客学习一下吧
    githmb
        54
    githmb  
       214 天前
    啊?
    ignore
        55
    ignore  
       214 天前
    啊?
    VinsonGuo
        56
    VinsonGuo  
       214 天前 via iPhone
    @maxssy remove 也不是 On ,因为是对数组整体 arraycopy ,跑 benchmark 性能和 linkedlist 差不多
    qwerthhusn
        57
    qwerthhusn  
       214 天前
    不要直接喷 OP ,有可能真的答不出来,之前就有司马面试官问到为啥数组能够快速访问数据,我感觉他是想往底层 JVM 指令甚至操作系统,计算机组成原理上问。

    Java 字节码中访问数组的指令是 aload (对象引用数组), bload ( boolean 数组),iload ( int 数组)等,就是访问 arr[n]其实只用到一个 JVM 指令,JVM 栈顶是数组的地址和 n 这个 int 数字,然后执行 xload 指令,弹出这两个东西,得到结果,将值压入栈,栈顶就是 arr[n]的值。所以数组元素的访问只有一个 JVM 指令,无论 n 多大。

    JVM 是虚拟机,xload 指令由 JVM 实际调用的什么呢?会不会有可能虽然 java 字节码只是一个指令,但是 jvm 解释后传递给下层的时候又变成循环了呢?

    我也编不出来了,什么操作系统虚拟内存/物理内存,内存页,甚至到 CPU 指令如何存取内存数据等等,都忘光了。反正就是从高层到底层,访问 arr[n]不会随着 n 变大出现时间增长。
    good1uck
        58
    good1uck  
       214 天前 via Android
    很多人答不上技术问题
    然后就挑 op 的标题态度问题

    同样的问题问在 stackoverflow
    你们觉得会有这么多事 b 跳出来教育人么
    iBugOne
        59
    iBugOne  
       213 天前   ❤️ 1
    @good1uck
    很多人提不出好的技术问题
    然后就在标题里加“不服来辩”

    同样的标题发在 Stack Overflow
    你们觉得会有事 b 来理你吗
    chaosz
        60
    chaosz  
       213 天前
    钓鱼的吧
    good1uck
        61
    good1uck  
       213 天前 via Android
    @iBugOne 都不用发 stack 啊 就这楼里你看看 你还是有人能说清楚 高下立判
    rOrange
        62
    rOrange  
       213 天前
    好好读读源码,连 linkedList 作者都发帖说不用 linkedList
    lyxeno
        63
    lyxeno  
       213 天前
    @qwerthhusn 这么一看,操作系统和 JVM 帮普通的程序员做了太多太多了
    lmq2582609
        64
    lmq2582609  
       213 天前
    可以看看数据在内存中是如何布局的
    fengyouliang
        65
    fengyouliang  
       209 天前
    玩会原神吧
    guguji
        66
    guguji  
    OP
       187 天前
    嗐 原来大家都在第一层~(我感觉没表达清楚问题),匿了匿了 害怕
    258
        67
    258  
       70 天前
    嗯?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5414 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 07:50 · PVG 15:50 · LAX 23:50 · JFK 02:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.