栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java 数组与ArrayList

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java 数组与ArrayList

Java 数组与ArrayList
  • 数组
    • 什么是数组?
    • 为什么没有看见定义?
  • ArrayList
    • 基于什么实现?
    • 查找/插入/删除时间复杂度
    • 源码:
      • add源码:
      • remove源码:
  • 扩展
    • 什么是RandomAccess?
    • 什么是标记接口,JDK中有那些?
    • 注:

数组 什么是数组?

JVM原生提供的定长数据结构,类型安全的

为什么没有看见定义?

JVM提供了虚拟机级别的支持,有对应的字节码.
相当于虚拟机层面定义了一个数组类,限制了类型,有插入和获取指定位置元素的方法.(可以这样子理解但是不存在这个类)
有专门指令来操作数组.
JVM中"["表示数组

ArrayList 基于什么实现?

数组

查找/插入/删除时间复杂度
  • 查找:O(1) 可以实现随机查找,查找任何一个数都是常数时间
    • 数组的寻址操作时间复杂度是O(1)的.因为内存中这是硬件电路实现的,可以无视数据量,直接定位到一个内存单元.
  • 插入:O(n) 往头插一个元素,需要把原有这个位置的元素及之后的所有元素往后移动一位.
  • 删除:O(n) 删除也类似,删除一个要将后面的元素往前移动
  • 扩容是如何实现的?
    • X1.5倍
    • 拷贝 例子:电话本满了,买一本大1.5倍的然后把旧的和新增加的抄写进去.
    • 执行add方法的时候判断
源码:

添加/删除/扩容/并发访问
add 添加元素,扩容操作(*1.5)
remove 删除元素,删除中间一个元素,要把后面往前补,如果删除最后一个,就只减一下下标.然后将最后一个空间设置成null(用于去除强引用,让无用的最后一个元素被GC)
checkForComodification() 检查并发访问的方法.用于操作集合过程中检查是否被并发访问的方法.防止出现并发操作集合.现在操作的数量和预期的不一致就表示出现并发访问.

add源码:
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中二分查找方法就判断了是否实现了这个接口,如果实现了就用基于下标的查找方法,如果没有则使用基于迭代器的查找方法.

什么是标记接口,JDK中有那些?

jvm中用于标记一个东西可以被某些功能使用,但是它没有提供任何实现方法.
Cloneable
Serializable

标记接口是计算机科学中的一种设计思路。编程语言本身不支持为类维护元数据。而标记接口则弥补了这个功能上的缺失——一个类实现某个没有任何方法的标记接口,实际上标记接口从某种意义上说就成为了这个类的元数据之一。运行时,通过编程语言的反射机制,我们就可以在代码里拿到这种元数据。

注:

O(1)无论数据规模如何,查找的时间消耗都是一样的常数.

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959500.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号