基础很差去公司做网站,网站开发常见问题总结,wordpress导入excel,广东网站设计与建设ArrayList、LinkedList、HashMap等集合#xff0c;从其前缀可知其对应的数据结构为数组、链表、哈希表。从数据结构#xff0c;也可反推出集合的结构。 文章目录 1、算法复杂度分析1.1 时间复杂度1.2 常见复杂度1.3 空间复杂度 2、数组2.1 内存寻址2.2 查找元素的时间复杂度2… ArrayList、LinkedList、HashMap等集合从其前缀可知其对应的数据结构为数组、链表、哈希表。从数据结构也可反推出集合的结构。 文章目录 1、算法复杂度分析1.1 时间复杂度1.2 常见复杂度1.3 空间复杂度 2、数组2.1 内存寻址2.2 查找元素的时间复杂度2.2 增删元素的时间复杂度 3、ArrayList源码3.1 成员变量部分3.2 构造方法部分3.3 添加数据和扩容 4、ArrayList底层的实现原理5、实现数组和List之间的转换 1、算法复杂度分析
时间复杂度评估代码的执行耗时与数据规模n的关系空间复杂度内存占用与数据规模n的关系
1.1 时间复杂度 以上有3 * n 3 行代码假设每行执行耗费1ms则总耗时
T(n) (3n 3) * 1ms时间复杂度即表示代码执行时间与数据规模n变化的趋势 ⇒ 大O表示法 ⇒
T(n) O(3n 3)因为表示的是一种趋势因此去掉系数和常数 得出
T(n) O(n)1.2 常见复杂度
总结常对幂指阶 如O(1)性能最好即数据变多执行耗时还是不变或者说代码行数是固定的。
如下只要代码的执行时间不随着n的增大而增大这样的代码复杂度都是O(1) 第二个例子中虽然有循环但其次数固定是100是i 100而不是i n因此复杂度仍然为O(1) 例2 例3 此时代码的执行和数据规模n的关系如下。因此时间复杂度为O(log n) 同理以下的实现复杂度也算为O(log n) 例4O(n)复杂度的方法调用了O(log n)复杂度的方法因此test05方法的时间复杂度为O(n * log n) 1.3 空间复杂度
如下两个局部变量i和sum不管n等于多少循环多少次都占这两个变量的空间因此空间复杂度为O(1) 如下数据规模n影响数组长度也即空间大小因此空间复杂度为O(n) 2、数组
2.1 内存寻址
用连续的内存空间存储相同数据类型元素的线性数据结构。数组变量的值指向0号元素的首地址。 取array[3]的值时即计算索引为3的元素的内存地址
//寻址
a[i] baseAddress i * dataTypeSize//baseAddress数组首地址如图中的10
//dataTypeSize数组中元素类型的大小如int时该值为44 byte这也是数组下标从0开始的原因让CPU少做一次减法运算
//寻址下标从0开始
a[i] baseAddress i * dataTypeSize//寻址下标从1开始
a[i] baseAddress i - 1 * dataTypeSize2.2 查找元素的时间复杂度
根据索引查时有寻址公式直接定位复杂度为O(1) 未知索引比如找值为55的这个元素。不排序就得遍历时间复杂度为O(n)。排序后二分查找时间复杂度为O(log n)
2.2 增删元素的时间复杂度
数组是一段连续的空间因此插入或删除元素其他元素会前移或者后退时间复杂度为O(n) 3、ArrayList源码
3.1 成员变量部分
elementData这个Object类型的数组是真正存储集合中元素的地方size元素个数 3.2 构造方法部分
无参构造默认elementData是一个空数组{}。传入一个初始化容量的有参构造逻辑为传入的容量大于0时给elementData复制一个对应长度的数组等于0则给elementData赋值空数组 接收一个Collection单列集合的父类的参数将 collection 对象转换成数组然后将数组的地址的赋给 elementData 3.3 添加数据和扩容
添加数据和扩容的基本思路为add前先确保容量size 1够不够size为当前元素个数size 1如果超过了elementData数组的长度就需要扩容。扩容时elementData长度 elementData长度右移一位除以2然后将原elementData拷贝到新容量的elementData数组中
ListInteger list new ArrayList();
list.add(1);
for (int i 2; i 10; i) {list.add(i);
}
list.add(11);以上用了无参构造因此elementData是一个空数组{}。第一次add的时候调用扩容方法的判断条件成立扩容到10 往后第2次 ~ 第10次add数据时均不需扩容。比如第十次add 第十一次add时elementData长度为第一次扩容的10而size 1为11了大于了elementData.length扩容。新容量为
elementData.length (elementData.length 1)
//10 10 1 10 10/2 1510扩容为15约1.5倍底层的elementData数组拷贝到一个长度为15的新数组 4、ArrayList底层的实现原理
ArrayList底层是一个数组elementData属性ArrayList初始容量为0elementData为空数组{}当第一次添加数据时才会初始化容量为10ArrayList扩容的时候容量为原容量的1.5倍且每次扩容都需要拷贝数组
调用add添加数据的时候逻辑如下
确保能存下 下一个数据判断逻辑是数组已使用长度(size) 1 后是否大于elementData数组的长度size 1 elementData.length则调用grow方法扩容反之则直接放进去
ArrayList myList new ArrayList(10);以上写法list扩容0次因为指定了容量为10elementData数组不再是空数组{ }因此第一次add时不会再扩容。 5、实现数组和List之间的转换 数组转List使用java.util.Arrays工具类的asList方法List转数组调用其toArray方法传参为带list长度的一个空数组 用 Arrays.asList 将数组转List 后如果修改了数组内容则由数组转来的List也会跟着变 测试代码 原因Arrays工具类底层用静态内部类ArrayList将传入的数组进行了包装最终指向的都是同一个内存地址。也就是说数组转List后List底层的数组还是指向原数组 调用toArray方法将List转为数组此时再修改List由List转来的数组并不跟着变 原因调用了 toArray 以后返回的是对ArrayList的elementData数组进行的拷贝
