这是一个创建于 874 天前的主题，其中的信息可能已经有所发展或是发生改变。
get(int index) 方法时间复杂度 O(1)，如何做的到？ - 如果底层是基于数组，那么数组为什么可以根据索引快速访问到数据？
remove(int index) 方法时间复杂度 O(N2) - 如果有大批量的数据在 list 中，且要删除其中一个元素，请问如何优化？ - 就基于 ArrayList 来做，不该变成 LinkedList 这种？
第 1 条附言 2023-08-25 17:13:03 +08:00
，理解偏差，我也不是闲人，标题确实有引战嫌疑。。。道歉
增加下场景大家明白了，没必要这样~
这个两个问题其实是某个面试官的问题，我觉得很清奇
我详细明确下前因后果：
1.get 问题
问：get 为何能快速找到
答：连续内存地址，a[i] = arr 起始地址 + 数组元素大小累加
问：知道地址就能找到？操作系统了解么
答：。。。
第一个问题我没想到会问到操作系统层面，感觉没必要，可能想要一杆子打到底。。。
2. remove
问：为何删除会慢
答：删除会挪动数组，效率差
问：有啥优化办法？
答：可以使用 linkedlist ，不过 get 会耗时，如果要达到 o(1)的话，可以 hash+linkedlist 。
问：假设就基于 arraylist 接口，且数据量很大，如何提升删除效率
答：。。。
关于问题 2 ，我觉得可以参考 hashmap 的原理来实现，数组内存储的不是元素，而是链表 or 红黑树。
没啥其他的想法，。。
如果限定条件是只能用 arraylist ，如何来提升 remove 的效率呢？大牛们可以 show 了~
增加下场景大家明白了，没必要这样~
这个两个问题其实是某个面试官的问题，我觉得很清奇
我详细明确下前因后果：
1.get 问题
问：get 为何能快速找到
答：连续内存地址，a[i] = arr 起始地址 + 数组元素大小累加
问：知道地址就能找到？操作系统了解么
答：。。。
第一个问题我没想到会问到操作系统层面，感觉没必要，可能想要一杆子打到底。。。
2. remove
问：为何删除会慢
答：删除会挪动数组，效率差
问：有啥优化办法？
答：可以使用 linkedlist ，不过 get 会耗时，如果要达到 o(1)的话，可以 hash+linkedlist 。
问：假设就基于 arraylist 接口，且数据量很大，如何提升删除效率
答：。。。
关于问题 2 ，我觉得可以参考 hashmap 的原理来实现，数组内存储的不是元素，而是链表 or 红黑树。
没啥其他的想法，。。
如果限定条件是只能用 arraylist ，如何来提升 remove 的效率呢？大牛们可以 show 了~
68 条回复 2025-04-23 10:54:40 +08:00
 | 1 Masoud2023 2023-07-28 16:55:32 +08:00  64 你这个问题应该回学校好好学学数据结构，而不是在这不服来辩 |
 | 2 thevita 2023-07-28 16:58:47 +08:00 1 要辩你应该先陈述自己的观点，不应该是问句 ps: remove(int index) 复杂度 O(N2) 写错了吧。remove(Object o) 才是 O(N^2) |
 | 3 me1onsoda 2023-07-28 17:00:56 +08:00 2 那么数组为什么可以根据索引快速访问到数据？ 大哥，数组存的数据在内存是连续的，当然可以根据索引来快速检索 |
 | 5 emSaVya 2023-07-28 17:04:12 +08:00 16 这位更是重量级。 |
 | 6 gangoogle 2023-07-28 17:04:26 +08:00/span> 1 数组在内存里面 第一个位置 0x0 第二个 0x2 我想取第 10 个元素直接 0x0+9 不就直接拿到了吗。。。。 |
 | 7 xaplux 2023-07-28 17:08:09 +08:00 额，哪来的勇气啊，数组存储是连续的 get 根据下标直接可以寻址了 remove 时间复杂度是 O(n) ,主要是删除一个元素后，其之后的元素要移动啊，如果删除的是最好一个元素，复杂度可以做到 O(1) |
 | 8 a0210077 2023-07-28 17:11:05 +08:00 服，请参考数据结构的数组章节 |
| 9 xaplux 2023-07-28 17:11:24 +08:00 ArrayList 和 LinkedList 的使用场景是不一样的，鱼和熊掌不可兼得，所以要权衡 如果需要频繁删除，那用 LinkedList 相对 ArrayList 要合适 |
 | 10 fresco 2023-07-28 17:11:25 +08:00 这不是大学的内容么 |
 | 11 PVXLL 2023-07-28 17:12:21 +08:00 1 震惊～ |
 | 13 Ayanokouji 2023-07-28 17:14:41 +08:00 不会的话，虚心请教不行吗，非要起这么一个标题找喷 |
 | 14 hidemyself 2023-07-28 17:15:09 +08:00 我怀疑你是来钓鱼的。 |
 | 16 Deeymmm 2023-07-28 17:18:41 +08:00 挺好，又 block 一个人 |
 | 17 xtreme1 2023-07-28 17:19:02 +08:00 钓的是_, 没的是_ |
 | 18 swczxf 2023-07-28 17:21:16 +08:00 via iPhone 这是不是叫民科 |
 | 19 Jrue0011 2023-07-28 17:24:05 +08:00 额，看历史发帖和回复也不应该啊 |
 | 20 mdn 2023-07-28 17:25:22 +08:00 不服来辩 === 求求大家告诉我答案 |
 | 21 deplivesb 2023-07-28 17:26:58 +08:00 op 的 blog 和他的三个帖子，看出来就是个 xx |
 | 22 Ericcccccccc 2023-07-28 17:29:06 +08:00 重新学下组成原理? |
 | 23 issakchill 2023-07-28 17:30:14 +08:00 为啥不问问神奇的 chatgpt? |
 | 24 coderxy 2023-07-28 17:35:41 +08:00 我原来面试别人的时候，不少人分不清数组跟链表的区别的时候我的心理活动跟现在一模一样的 |
 | 25 itechify PRO 钓鱼贴 |
 | 26 maxssy 2023-07-28 17:51:12 +08:00 1 1. ArrayList 的首个元素的地址是已知的 2. ArrayList 底层实现在内存上表现为各个元素顺序排放的数组 3. ArrayList 每个元素的内存占用大小是已知的 所以 get 在取得索引后可以通过公式: `目标元素的地址 = 首元素地址 + 索引 * 每个元素的内存占用大小` 来取得, 所以时间复杂度是 O(1) 又因为各元素是顺序排放的, remove 某个元素后需要重新排列整个数组, 所以是 O(n) |
 | 27 cyndihuifei 2023-07-28 17:52:44 +08:00 为什么这种问题都搞不清楚还要发技术文章 |
 | 28 dragondove 2023-07-28 18:23:05 +08:00 3 @xaplux 实际上 LinkedList 已经基本没有适合使用的地方了，具体可以看这个知乎回答 https://www.zhihu.com/question/563680801/answer/2750393567 |
 | 29 zengmingyang96 2023-07-28 18:48:17 +08:00 数组为什么可以根据索引快速访问到数据? 因为内存支持随机读取 |
 | 31 neptuno 2023-07-28 18:55:46 +08:00 via iPhone 我一般都是钻到内存里面，自己去找地址 |
 | 32 BeautifulSoap 2023-07-28 18:59:53 +08:00 via Android 本来以为 lz 想要问的是内存电路是怎么寻址的，实但仔细想想 lz 可能真的连数组是啥都不懂。。。 |
| 33 itechify PRO @dragondove 偶尔还是会用到的，不确定数量情况下 |
 | 34 dk7952638 2023-07-28 19:23:12 +08:00 看这标题，以为来到了贴吧 |
 | 35 xiangbohua 2023-07-28 19:37:12 +08:00 你说了几个问题，你都没给结论，辩论啥 |
 | 36 haolongsun 2023-07-28 19:37:52 +08:00 没上过数据结构？底层是数组，再细说是对数组首地址的引用，快速访问到素就是首地址+偏移量*数组元素 sizeof,这就是 O(1)，再多说就是 arraylist 的结构就是一个指向堆上数组的指针，一个 len ，一个 cap 。 |
 | 37 BanGanExpert 2023-07-28 19:38:28 +08:00 @v2eb 以前本身业务需求多，JavaWeb 上手不又难，造成很多基础不扎实，不清楚基本的数据结构知识，很多人也能进入行业做开发。当然现在新人水平普遍是专业对口毕业的，自然很大程度上都没这个情况了。我以前面试人一般第一个问题就是，你写 Java 用了哪些线性结构的集合实现，分别在哪种场景，除了当普通集合还能干嘛（ Stack 、Heap 、Queue ）。 |
 | 38 xhinliang 2023-07-28 19:40:28 +08:00 挺好，又 block 一个人 |
 | 39 strrng 2023-07-28 19:43:00 +08:00 OP 感觉多少是有点搞笑了 |
 | 40 zcm3579 2023-07-28 19:50:51 +08:00 辩了个勾巴 , 脑残就不要发帖 |
 | 41 Cooky 2023-07-28 20:04:06 +08:00 看来裁员裁的还不够多 |
 | 42 makelove 2023-07-28 20:24:14 +08:00 你不适合这个职业，趁早转行 |
 | 43 zhch602 2023-07-28 23:25:16 +08:00 via iPhone 这时候就看出来第一门语言学 C 的好处了不会问出这种弱智问题 |
 | 44 Yadomin 2023-07-29 01:09:45 +08:00 via Android |
 | 45 idealhs 2023-07-29 01:27:57 +08:00 1 跟个弱智一样 |
 | 46 IvanLi127 2023-07-29 01:45:36 +08:00 via Android 什么鬼。。。这问题能问得出口？这属于话不会说，代码也不懂写。 |
 | 47 Qzier 2023-07-29 03:09:49 +08:00 via iPhone 培训班出来的？没学过数据结构吗？ |
 | 48 NoKey 2023-07-29 09:42:47 +08:00 为啥不问问神奇的 chatgpt? |
 | 49 learningman 2023-07-29 10:39:29 +08:00 via Android 搞 Java 搞的 |
 | 50 kachu673 2023-07-29 13:14:40 +08:00 原来真有程序员不懂这些东西。。。可见科班的重要性了 |
 | 51 4kingRAS 2023-07-29 14:40:04 +08:00 类似你找车位，数组就是车位有刷编号，那不就 O (1) 找到了吗 |
 | 52 kylix 2023-07-29 15:10:32 +08:00 OP 抛了问题后，匿了 |
 | 53 czzhengkw 2023-07-29 16:00:46 +08:00 |
 | 54 githmb 2023-07-29 20:18:58 +08:00 啊? |
 | 55 ignore 2023-07-29 21:06:16 +08:00 啊? |
 | 56 VinsonGuo 2023-07-30 00:24:30 +08:00 via iPhone @maxssy remove 也不是 On ，因为是对数组整体 arraycopy ，跑 benchmark 性能和 linkedlist 差不多 |
 | 57 qwerthhusn 2023-07-30 10:36:00 +08:00 不要直接喷 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 变大出现时间增长。 |
 | 58 good1uck 2023-07-30 15:41:04 +08:00 via Android 很多人答不上技术问题 然后就挑 op 的标题态度问题 同样的问题问在 stackoverflow 你们觉得会有这么多事 b 跳出来教育人么 |
 | 59 iBugOne 2023-07-30 17:22:08 +08:00 1 |
 | 60 chaosz 2023-07-30 19:18:17 +08:00 钓鱼的吧 |
 | 62 rOrange 2023-07-31 00:40:50 +08:00 好好读读源码，连 linkedList 作者都发帖说不用 linkedList |
 | 63 lyxeno 2023-07-31 09:07:59 +08:00 @qwerthhusn 这么一看，操作系统和 JVM 帮普通的程序员做了太多太多了 |
 | 64 dongdong12345 2023-07-31 09:41:26 +08:00 可以看看数据在内存中是如何布局的 |
 | 65 fengyouliang 2023-08-04 15:39:28 +08:00 玩会原神吧 |
 | 66 guguji OP 原来大家都在第一层~（我感觉没表达清楚问题），匿了匿了 害怕 |
 | 67 258 2023-12-21 10:08:57 +08:00 嗯？ |
 | 68 sz065vHi2V1c6LKP 239 天前 @Livid ，id 为 idealhs 的 45 楼，辱骂他人。 |
Select Language