数组知识

数组知识

这是崔斯特的第一百二十一篇原创文章

努力、奋斗

数组看起来简单基础,但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号,而不是从1开始的问题,进入主题。

数组如何实现随机访问

  1. 数组是一种线性数据结构,用连续的存储空间存储相同类型数据
  2. 线性表:数组、链表、队列、栈;非线性表:树、图
  3. 连续的内存空间、相同的数据,所以数组可以随机访问,但对数组进行删除插入,为了保证数组的连续性,就要做大量的数据搬移工作
    1. 数组如何实现下标随机访问。引入数组再内存种的分配图,得出寻址公式
    2. 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组,用二分查找,时间复杂度也是O(logn)。正确表述:数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

低效的插入和删除

  1. 插入:从最好O(1) 最坏O(n) 平均O(n)
  2. 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。作者举例说明
  3. 删除:从最好O(1) 最坏O(n) 平均O(n)
  4. 多次删除集中在一起,提高删除效率

记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即 JVM 标记清除垃圾回收算法。

警惕数组的访问越界问题

用C语言循环越界访问的例子说明访问越界的bug。此例在《C陷阱与缺陷》出现过,很惭愧,看过但是现在也只有一丢丢印象。翻了下书,替作者加上一句

话:如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存,那么内存中的i将会被置为0,则为死循环永远出不去。

容器能否完全替代数组

相比于数字,java中的ArrayList封装了数组的很多操作,并支持动态扩容。一旦超过村塾容量,扩容时比较耗内存,因为涉及到内存申请和数据搬移。

数组适合的场景:

  1. Java ArrayList 的使用涉及装箱拆箱,有一定的性能损耗,如果特别管柱性能,可以考虑数组
  2. 若数据大小事先已知,并且涉及的数据操作非常简单,可以使用数组
  3. 表示多维数组时,数组往往更加直观
  4. 业务开发容器即可;底层开发,如网络框架,性能优化,选择数组。

原文 

https://zhangslob.github.io/2020/04/19/数组知识/

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 数组知识

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址