专栏首页搜云库技术团队数组是如何随机访问元素?数组下标为什么从0开始,而不是1?

数组是如何随机访问元素?数组下标为什么从0开始,而不是1?

数组如何实现随机访问元素

什么是数组?

数组(Array)是一种线性表数据结构,它用一组连续的内存空间,来存储相同类型的数据。

什么是线性表(Linear List)?

线性表就是数据排成一条线一样的结构,每个线性表的数据最多只有前后两个方向。

例如:数组,链表,队列,栈 等都是线性表结构。

什么是非线性表?

例如:二叉树,堆,图,等,是非线性表,是因为,在非线性表中,数据之间并不是简单的前后关系。

数组是如何随机访问数组元素?

数组是如何实现根据下标随机访问数组元素的吗?

例如: int[]a=newint[10]

1,计算机给数组a[10],分配了一组连续的内存空间。 2,比如内存块的首地址为 base_address=1000。 3,当计算给每个内存单元分配一个地址,计算机通过地址来访问数据。当计算机需要访问数组的某个元素的时候,会通过一个寻址公式来计算存储的内存地址。

公式如下:

a[i]_address = base_address + i * data_type_size

arr[i] 首地址 = 数组内存块首地址 + 数据类型大小 * i ,其中i为偏移量。

baseaddress:内存块的首地址。datatype_size:数组中每个元素的大小,比如每个元素大小是4个字节。

1,数组使用二分法查找元素,时间复杂度是O(logn)。 2,根据下标随机访问的时间复杂度是O(1)。

低效的“插入”和“删除”

插入

插入:从最好O(1) 最坏O(n) 平均O(n)

什么时候会是O(1)?

数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把新的元素,插入到第k个位置,此处复杂度为O(1)。

例如:a[10] 数组存储了5个元素: A B C D E

我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5],将 a[2] 赋值为 x 即可。

最后,数组中的元素如下: A,C,X,D,E,C

什么时候会是最坏O(n)?

从数组开头插入数据,所有的数据往后移一位,情况最差,时间复杂度为O(n) 。 每一位插入的概率一样,所以平均时间复杂度为 (1+2+...+n)/n=(1+n)/2=O(n)

删除

删除:从最好O(1) 最坏O(n) 平均O(n)

和插入数据类似,如果我们要删除 K 个位置的数据,要保证内存的连续性,我们需要搬移 K 位置后的所有数据往前移动一位。

什么时候会是O(1)?

删除开头的数据

什么时候会是最坏O(n)?

同数组插入的原理类似

数组如何提高效率?

将多次删除操作中集中在一起执行,可以先记录已经删除的数据,但是不进行数据迁移,而仅仅是记录,当发现没有更多空间存储时,再执行真正的删除操作,这样减少数据搬移次数节省耗时。

这也是跟 JVM 标记清除垃圾回收算法的核心思想相似

标记-整理垃圾回收算法

在垃圾收集时此算法分为“标记”、“清除”两个阶段,先标记出需要回收的对象,再统一清除标记的对象。清除之后会产生大量不连续的内存碎片。

标记-整理垃圾回收算法

在标记完成之后让所有存活的对象都向一端移动,然后直接清理掉边界以外的内存。

用数组还是容器?

数组先指定容器大小,容器ArrayList可以动态扩容,并且封装了好多方法,一旦超过存储容量,扩容时比较耗时,因为涉及内存申请和数据复制搬移到扩容后的数组。

1,如果已知数据大小,且涉及的数据操作比较简单,可以用数组。 2,比如已知 1 万条数据要存入 ArrayList,我们就可以事先指定容器大小。

例如下代码,就可以,省掉多次的,内存申请,和数据搬移操作

ArrayList<User> users = new ArrayList(10000);for (int i = 0; i < 10000; ++i) {  users.add(xxx);}

3,容器无法存储基本类型,比如 int long 需要转换成包装类型,类型的转换有性能消耗。 4,业务开发,使用容器足够,追求性能,首先用数组。

为什么数组要从 0 开始编号,而不是1?

从偏移角度理解a[0] 0为偏移量,如果从1计数,会多出K-1。增加cpu负担。为什么循环要写成 for(inti=0;i<3;i++)而不是 for(inti=0;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据,而后者 2-0+1个数据,多出1个加法运算,很恼火。

参考:《数据结构与算法之美》

更多技术干货

近期100多篇技术干货,升职加薪必看

数据库架构:分库分表-垂直?水平?

数据库架构:主备+分库?主从+读写分离?

Web系统大规模并发:电商秒杀与抢购

秒杀系统架构优化思路

专业解决 MySQL 查询速度慢与性能差

从单体应用,微服务,容器化,的架构演进之路

面试中经常被问到的 Redis 持久化与恢复

本文分享自微信公众号 - 搜云库技术团队(souyunku),作者:鹏磊

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你还在new对象吗?Java8通用Builder了解一下?

    这个示例最多支持三个参数的设置属性方法,也完全够用了。如果要扩展也很容易,依葫芦画瓢,添加多个参数的Consumer。

    搜云库技术团队
  • 面试必备:基于 Zookeeper 的分布式锁实现【图文并茂 附源码 】

    最近在学习 Zookeeper,在刚开始接触 Zookeeper 的时候,完全不知道 Zookeeper 有什么用。且很多资料都是将 Zookeeper 描述成...

    搜云库技术团队
  • 还没用上 JDK 11吧,JDK 12 早期访问构建版使用

    JDK 更新速度快的飞起,JDK 12 早期访问构建版已发布,你现在用到了第几版本?

    搜云库技术团队
  • Python NumPy 基础

    这两天读完《利用Python进行数据分析》 这本书的第4章:NumPy 基础:数组和矢量计算 后,在进行下一步阅读高级应用前,先整理本章内容,做个笔记备查,也好...

    Alan Lee
  • Day 1-Java-imooc-5.数组

    课程地址:http://www.imooc.com/learn/85 总结图片来自 http://www.imooc.com/article/10535 ? -...

    杨熹
  • Java基础系列(五):数组

    在Java中,有一种数据结构叫做数组,它用来存储同一类型的值的集合。通过一个整型下标可以访问数组中的每一个值。例如,如果a是一个整型数组,那么a[i]就是数组中...

    山禾说
  • 数据结构与算法学习笔记之 从0编号的数组

    数组看似简单,但掌握精髓的却没有多少;他既是编程语言中的数据类型,又是最基础的数据结构;

    Dawnzhang
  • Java漫谈-数组

    在Java语言中,数组是对象(An object is a class instance or an array.),而且是动态创建的。

    汐楓
  • Java 多维数组遍历

    数组是Java中的一种容器对象,它拥有多个单一类型的值。当数组被创建的时候数组长度就已经确定了。在创建之后,其长度是固定的。下面是一个长度为10的数组:

    哲洛不闹
  • 数组方法整理

    mcq

扫码关注云+社区

领取腾讯云代金券