01｜动态数组：按需分配的vector为什么要二倍扩容？
该思维导图由 AI 生成，仅供参考
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
动态数组的实现原理及优势 本文深入探讨了动态数组的实现原理和优势。首先介绍了静态数组在插入和删除操作上的低效性，由此引出了动态数组的必要性。动态数组通过自动扩容的方式，封装了繁琐的细节，提高了使用体验和效率。文章还分析了STL中vector的源码，介绍了动态数组在内存中的表示和扩容机制。通过对动态数组的原理和实现进行分析，读者可以深入了解动态数组的工作原理和优势。 在实验中观察到，动态数组的扩容方式采用倍增策略，即每次将容量扩展为当前的一倍。这种策略能够显著降低时间复杂度，使得插入N个元素的复杂度降为O(N)，极大提升了效率。相比之下，采用固定大小的容量扩展或每次只扩展一个元素都会导致较高的时间复杂度，不够合理。 通过对动态数组的实现原理和扩容逻辑进行分析，读者可以深入理解动态数组的工作机制。动态数组在内存中的连续存储特性使得其支持O(1)基于下标的随机访问，而内置的倍增扩容策略则使其看起来像是具有无限容量。这使得动态数组在需要频繁查询、变更但很少插入/删除的场景中得到广泛应用，例如在实现一个简单的Web服务器时，可以用vector来存储handler的线程，达到线程复用的效果。 通过深入了解动态数组的实现原理，读者可以在日常开发中更好地理解不同数据结构可能带来的性能瓶颈，为数据结构的选择提供更加深入的依据。文章内容简洁明了，为读者提供了对动态数组的全面了解，使其能够更好地应用于实际开发中。
《业务开发算法 50 讲》，新⼈⾸单¥59
全部留言(17)
- 最新
- 精选
qinsi两倍扩容的问题在于无法利用已释放的空间，因为假设第n次扩容分配了2^n的空间（省略常数C），那么之前释放掉的空间总和为： 1 + 2 + 2^2 + ... + 2^(n-1) = 2^n - 1 正好放不下2^n的空间。这样导致的结果就是需要操作系统不断分配新的内存页，并且数组的首地址也在不断变大，造成缓存缺失。 假设扩容倍率为x，首次分配的空间为1（同样省略常数C），则第一次扩容分配的空间为x，第二次扩容分配的空间为x^2。如果希望第二次扩容正好能用上之前申请过的空间，则有： 1 + x = x^2 解得x=(1+sqrt(5))/2，约1.618 当然这是简化的分析，因为第二次扩容时要需要把第一次扩容的空间中的数据拷贝出来，所以至少要等到第三次扩容才行，也就是： 1 + x = x^3 更一般的： 1 + x + ... + x^(n - 2) = x^n 当n->∞时，x->1.618。所以实际会用比1.618小的值，否则n太大就没意义了。比如Java的ArrayList用的是1.5，那么第5次扩容时就可以利用旧的空间了。 当然这些也只是理论上的分析，实际情况要根据内存分配器的实现具体分析。作者回复: 学到了～
2021-12-15954
sc
在 Java 的 ArrayList 中，没有自动缩容，但是提供了一个 trimToSize() 的方法可以让使用者手动缩容；如果要设计自动缩容的话，可以简单设计成 size 减少到到 capacity/4 的时候，将容量缩减成原来的一半作者回复: 哈哈哈 学到了~
2021-12-1214- Paul Shan如果在存储空间占比低于一半的时候就缩容，会导致反复插入删除回到单步操作O(n)的复杂度，以前见过的实现是存储的空间占总空间的1/4的时候开始缩容一半，可以做到单步均摊复杂度O(1)。数组看似简单，实则精妙，平均浪费一半空间的时候，才能取得较好的性能，也算一种空间换时间的方法。
作者回复: 嗯嗯 设计就是在不断的权衡中一步步优化的
2021-12-136 - 木汀类似 golang 中的 slice，但是在 golang 中，当 slice 的大小<1024时，是2的指数幂次增加长度，但是在> 1024之后就是1.25倍，并做内存对齐操作。
作者回复: 写得很好哦！ 欢迎+v: constant_variation 知道为什么是1.25倍吗
2022-04-123 
Aliliingo 语言中提供的 slice 是不是就是动态数组呢，定义的时候，长度并不固定，可以向切片中追加元素，它会在容量不足时自动扩容。也提供了 len 和 cap 函数来获取长度和容量。 当然 go 中的 slice 扩容的方案，不是倍增的方式，而是他自己的算法，小于 1024 才会将容量翻倍，大于 1024 每次只是增加 25% 的容量。但 go 的 slice 扩容之后，会新申请一段内存，拷贝过去，你即便删除了扩容的部分，内容大小也不会变。这时候，因为你是新申请了一段内存，原来的数组用到的内容，一旦没地方引用，就自动释放了。。至于如何再通过缩小原有的内存空间，就不知道怎么搞了。😂，不过比起先导篇中，跟上数学课，笔掉地上再捡起来后就听不懂了的情况来说，这节课至少没分心。作者回复: 哈哈哈 总结的不错呀 对golang不是特别熟悉；学到了～
2021-12-1332- Space均摊下来是O(1)?? 怎么算出来的的？(2^(x+1) - 1 ) / x == O(1)???? 别逗我
作者回复: 2^(x+1) = 2*2^(x) = 2 * n / n = O(1) 这位同学注意 x 并不是 n 而是 log(n) 哦
2022-03-241 
奋青。所以如果我们要插入 n 个元素，需要进行的拷贝次数：1+2+3+…+n=n2复杂度为 O(n^2)，均摊下来每次操作时间复杂度就是 O(n)。 这句话里面的 o(n^2) 是怎么计算得到的呀.作者回复: 就是小学二年级学过的等差数列求和哦
2021-12-1531
丶二倍扩容后，插入数据的均摊时间复杂度不应该是log（n）吗？？？整体均摊扩容也应该是log（n）吧？？计算如下：插入n个数据，需要需要log（n）次扩容，每次扩容需要转移元素时间复杂度为O（n）。这样插入数据总的时间复杂度就是 n + nlog（n），然后均摊到每一次就是 1 + log（n），最后时间复杂度不应该是log（n）吗？？？类似的插入元素时间复杂度为O（logn）。上面是我的理解，如果有错误，希望指正作者回复: 但是logn次扩容不是每次扩容所需要的复杂度都是n呀；而是n/2，n/4，n/8...1
2021-12-23
友自己总结一下：按照1扩容 那么 1+2+3+4 > 8 其实越往后拷贝的越来越多 每次扩容要拷贝的越来越多，但是之前我疑惑我把数值调大不就行了吗，第一浪费空间不说，可以继续算一下从1->4 那么每次就是 1+5+9+13+17+21+25 扩容到25需要6次,如果是按1扩容那么就是24次 那么就是减少了C倍而已 当数值越来越大 在 扩容到17的时候应该复杂度就上去了 如果是翻倍扩容 那么 公式就是 1 + 2 + 4 ... +n < 2*n 均摊下来扩容就是O（1）了 以上是自己的一些小总结 有错误希望各位矫正作者回复: 说的没错 主流动态数组的实现都是倍增的策略哦
2021-12-14
kimoti看完这节感觉可以不至于从入门到放弃作者回复: 加油加油 https://github.com/wfnuser/Algorithms 可以多多尝试自己手写实现～
2021-12-14
