听书笔记：数据结构与算法之美(4)
Hi! 
什么是数组
数据(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表
顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组之外，链表、队列、栈也是线性表结构。 与之相对的是非线性表，比如二叉树、图、堆等，其数据之间并不是简单的前后关系。
连续的内存存储空间和相同类型的数据
这两个限制使它有了堪称杀手锏的特性：随机访问。但同时也造成了很多操作的低效性。比如插入和删除操作。
随机访问的实现
例子：长度为10的int型数据int a[] = new int[10];计算机会为数组a[10]分配一块连续的内存空间1000~1039，其中首地址为base_address = 1000;
当计算机要随机访问数组中的某个元素时它会首先通过下面的寻址公式，计算出该元素的存储的内存地址： a[i]_address = base_address + i * data_type_size
这个例子中的int类型是4字节，data_type_size = 4字节。
误区：数组和链表的区别：“链表适合插入和删除操作，时间复杂度是O(1)；数组适合查找，查找的时间复杂度是O(1)”
解释：数组适合查找操作，但是查找的时间复杂度并不为1.即便是排好序的数组用二分查找时间复杂度也是O(logn)。正确的表述是，数组支持随机访问，根据下标随机访问的时间复杂度是O(1);
低效的插入和删除
插入操作
如果在数组的末尾插入元素，则时间复杂度是O(1)，在数组的开头插入，需要把数组依次往后移动一位，所以最坏时间复杂度是O(n)；因为在每个位置插入的概率是一样的，所以平均情况的时间复杂度是(1+2+…+n)/n = O(n)；
如果数组是有序的，则插入操作必须按照刚才的方法搬移数据。但如果数据是无序的，只是作为一个存储数据的集合。在这种情况下在第k个位置插入，只需要把第k位的的数据搬移到数组元素的最后，然后把新的元素直接放入第k个位置。
这种处理思想在快排中有使用。
删除操作
和插入类似，删除末尾的元素，时间复杂度是O(1)，删除第一个元素的时间复杂度是O(n)，平均时间复杂度是O(n)。 我们可以先记录下已经删除的数据，每次的删除并不是真正的删除，当数组没有更多的存储空间时，我们在触发一次真正的删除操作，这样就大大的减少；额删除操作导致的数据搬移。
JVM的标记清除垃圾回收算法就是应用的这个思想。 很多时候我们并不是要去死记硬背某个数据结构或算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。
警惕数组访问越界的问题
数组越界在c语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为访问数组的本质就是访问一段连续的内存，只要数组通过偏移计算得到的内存是可用的，那么程序就可能不会报任何错误。这种情况下一般会出现莫名其妙的错误，很多计算机病毒这正是利用数组越界可用访问非法地址的漏洞来攻击系统的。
Java会做越界检查。
容器能否代替数组
ArrayList最大的优势就是可用将很多数组操作的细节封装起来，并且支持扩容。 扩容操作涉及到内存的申请和数据的搬移，是比较耗时的，所有如果实现确定需要的存储的数据大小，最好在创建ArrayList的时候事先指定数据的大小。
1、Java ArrayList无法存储基本数据类型，比如int、long，需要封装Integer、Long类，而AutoBoxing、UnBoxing则有一定的性能消耗，所有如果特别关注性能，或者希望使用基本数据类型就可以选择数组 2、如果数据大小事先已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组。 3、当要表示多维数组时，用数组往往会更加直观。
总结，对于业务开发，直接使用容器就足够了，省时省力。如果最一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这时候数组就会优于容器成为首选。
如何实现随机访问
Gist code
To use, see:Jektify - Doc
- jektify © 2019
-
Música
Goodbye! 
The word of the day!
Put a very powerful message.