- 数组
- 什么是数组?
- 为什么没有看见定义?
- ArrayList
- 基于什么实现?
- 查找/插入/删除时间复杂度
- 源码:
- add源码:
- remove源码:
- 扩展
- 什么是RandomAccess?
- 什么是标记接口,JDK中有那些?
- 注:
JVM原生提供的定长数据结构,类型安全的
为什么没有看见定义?JVM提供了虚拟机级别的支持,有对应的字节码.
相当于虚拟机层面定义了一个数组类,限制了类型,有插入和获取指定位置元素的方法.(可以这样子理解但是不存在这个类)
有专门指令来操作数组.
JVM中"["表示数组
数组
查找/插入/删除时间复杂度- 查找:O(1) 可以实现随机查找,查找任何一个数都是常数时间
- 数组的寻址操作时间复杂度是O(1)的.因为内存中这是硬件电路实现的,可以无视数据量,直接定位到一个内存单元.
- 插入:O(n) 往头插一个元素,需要把原有这个位置的元素及之后的所有元素往后移动一位.
- 删除:O(n) 删除也类似,删除一个要将后面的元素往前移动
- 扩容是如何实现的?
- X1.5倍
- 拷贝 例子:电话本满了,买一本大1.5倍的然后把旧的和新增加的抄写进去.
- 执行add方法的时候判断
添加/删除/扩容/并发访问
add 添加元素,扩容操作(*1.5)
remove 删除元素,删除中间一个元素,要把后面往前补,如果删除最后一个,就只减一下下标.然后将最后一个空间设置成null(用于去除强引用,让无用的最后一个元素被GC)
checkForComodification() 检查并发访问的方法.用于操作集合过程中检查是否被并发访问的方法.防止出现并发操作集合.现在操作的数量和预期的不一致就表示出现并发访问.
public boolean add(E e) {
// 确保数组容量足够方法
ensureCapacityInternal(size + 1); // Increments modCount!! (modCount计数增加 用于并发修改判断)
// 将元素添加进数组最后一个位置
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 是否是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 与默认值(DEFAULT_CAPACITY=10)比较取二者中大的
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 如果所需容量比当前容量大 则需要调用扩容方法
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 得到原始1.5倍的容量 newCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果newCapacity比所需容量小,则新的数组容量为 所需的最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// newCapacity 上面的步骤计算出来所需的扩容的容量如果超过了限制 MAX_ARRAY_SIZE int最大值-8
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 限制最大只能扩充到最大容量 minCapacity如果变成负数了(溢出),hugeCapacity方法会报错(OutOfMemoryError 内存不足)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:(minCapacity 通常接近 size,所以这是一个胜利:)
// 将原有的数组拷贝的容量更大的新数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
remove源码:
public E remove(int index) {
// 范围检查 下标不能超出范围
rangeCheck(index);
// modCount 要加一 用于检查并发修改的判断使用
modCount++;
// 取到要删除的元素
E oldValue = elementData(index);
// 计算要复制的数组元素的数量
int numMoved = size - index - 1;
if (numMoved > 0)
//将数组中index位置后面所有的元素都往前拷贝,补齐index下的空位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//清空最后一位元素的值,便于垃圾回收,防止还保有无用对象的强引用
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
扩展
什么是RandomAccess?
标记接口,表示支持随机访问.告诉别人自己支持快速的随机访问,用于实现快速算法.
比如Collections中二分查找方法就判断了是否实现了这个接口,如果实现了就用基于下标的查找方法,如果没有则使用基于迭代器的查找方法.
jvm中用于标记一个东西可以被某些功能使用,但是它没有提供任何实现方法.
Cloneable
Serializable
标记接口是计算机科学中的一种设计思路。编程语言本身不支持为类维护元数据。而标记接口则弥补了这个功能上的缺失——一个类实现某个没有任何方法的标记接口,实际上标记接口从某种意义上说就成为了这个类的元数据之一。运行时,通过编程语言的反射机制,我们就可以在代码里拿到这种元数据。
注:O(1)无论数据规模如何,查找的时间消耗都是一样的常数.



