数组知识
这是崔斯特的第一百二十一篇原创文章
努力、奋斗
数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。
数组如何实现随机访问
- 数组是一种线性数据结构，用连续的存储空间存储相同类型数据
- 线性表：数组、链表、队列、栈；非线性表：树、图
- 连续的内存空间、相同的数据，所以数组可以随机访问，但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作
- 数组如何实现下标随机访问。引入数组再内存种的分配图，得出寻址公式
- 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。正确表述：数组支持随机访问，根据下标随机访问的时间复杂度为O（1）
低效的插入和删除
- 插入：从最好O(1) 最坏O(n) 平均O(n)
- 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。作者举例说明
- 删除：从最好O(1) 最坏O(n) 平均O(n)
- 多次删除集中在一起，提高删除效率
记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即 JVM 标记清除垃圾回收算法。
警惕数组的访问越界问题
用C语言循环越界访问的例子说明访问越界的bug。此例在《C陷阱与缺陷》出现过，很惭愧，看过但是现在也只有一丢丢印象。翻了下书，替作者加上一句
话：如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存，那么内存中的i将会被置为0，则为死循环永远出不去。
容器能否完全替代数组
相比于数字，java中的ArrayList封装了数组的很多操作，并支持动态扩容。一旦超过村塾容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。
数组适合的场景：
- Java ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别管柱性能，可以考虑数组
- 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组
- 表示多维数组时，数组往往更加直观
- 业务开发容器即可；底层开发，如网络框架，性能优化，选择数组。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
