数组的扩容1.背景2.问题的提出、解决及思考3.总结

54 阅读 0 评论 36 点赞

我是靠谱客的博主重要酸奶，最近开发中收集的这篇文章主要介绍数组的扩容1.背景2.问题的提出、解决及思考3.总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.背景

数组是一种按照顺序存储的数据结构，通常在被创建之后，就不能被改变。若想要在原来的数组上面增加或者删除一些数据，就需要用到数组的扩容技术。通常是采用创建一个新数组，对数组进行以下增删改的操作，然后将原来数组的引用指向这个新创建的数组。

2.问题的提出、解决及思考

2.1 问题的提出

现在有一个int类型的数组arr，需要在指定的begin位置后面添加一个长度为num的数组need。通俗的说，就是需要将一个数组插入到原始数组的指定位置，获得一个新的数组。

2.2 问题的解决

作为一个初学者，在不懂调用java工具包或者使用相关函数的情况下，我先自己编写了一个小程序来实现这个简单的功能，可能网上会有更好的办法，欢迎大家一起讨论。

 public class addArray {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,8,3,5,4};
        System.out.println("原始的数组为："+ Arrays.toString(arr));
        int[] need = new int[]{2,3,4,7};
        System.out.println("插入的数组为："+Arrays.toString(need));
        int[] arr = add(3, 4, need, arr);
        System.out.println("插入后的数组为"+Arrays.toString(add));

    }
    public static int[] add(int begin,int num,int[] need,int[] org){
        int[] arrNew = new int[org.length+num];
        int index = begin;
        for (int i = 0; i < arrNew.length; i++) {
                if(i<=begin){
                    arrNew[i] = org[i];
                }else if(i<=begin+num){
                    arrNew[i]=need[i-begin-1];
                }else {
                    begin++;
                    arrNew[i] = org[begin];
                }
        }
        return arrNew;
        }
  }

2.3 问题的思考

对于数组扩容这个简单的问题，我查阅了网上的相关的一些比较常用的方法，总结如下：

利用数组复制的方式进行扩容(也就是上文中代码提到的方法)
System.arraycopy的方法进行扩容：

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
代码解释:
　　 Object src : 原数组
　　 int srcPos : 从元数据的起始位置开始
　　 Object dest : 目标数组
　　 int destPos : 目标数组的开始起始位置
　　 int length : 要copy的数组的长度

Arrays.copyOf()可以简便的创建数组副本

public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
代码解释：
　　 src：源数组
　　 srcPos: 从元数据的起始位置开始
　　 dest : 目标数组
　　 destPos: 目标数组的开始起始位置
　　 length: 要copy的数组的长度

2.4 扩展阅读

我们都知道，String类型是java中一种比较常用的引用类型，底层是用一个被final修饰的字符型数组，每一次对字符串进行增删改操作的时候都会创建一个新的字符串，这样很容易造成资源的浪费。而StrigBuffer/StringBuilder定义为字符串缓冲区，是可变长度的字符串。StringBuffer(jdk1.0): 线程安全，StringBuilder(jdk1.5):非线程安全。也就是说在单线程的情况下尽量使用StringBuilder，效率较高。当然，这里的主要问题，是想要研究一下StrigBuffer/StringBuilder是如何被定义为可变字符串的，底层的实现原理是什么？
首先StrigBuffer/StringBuilder都是继承自同一个类AbstractStringBuilder，下面对StringBuffer进行讨论：

  public StringBuffer(){
      super(16);
  }

可以看出，无参数的情况下，初始的StringBuffer的容量为16。

  public StringBuffer(String str){
      super(str.length()+16);
  }

有参数的情况下，初始的StringBuffer的容量为16+字符串的长度。也就是说，字符串在被创建的时候，就会将原始的字符串的容量扩展16。

  public AbstractStringBuilder append(String str){
      if(str==null)
          return appendNull();
      int len=str.length();
      ensureCapacityInternal(count+len);
      str.getChars(0,len,value,count);
      count+=len;
      return this;
  }

使用ensureCapacityInternal来判断，如果新增的字符串超过StringBuffer的容量（16+字符串长度），进行扩容的操作，int newCapacity = (value.length << 1) + 2。增加为自身长度的一倍然后再加2，如果还是不够大，那就直接扩容到它需要的长度newCapacity = minCapacity;

 private void ensureCapacityInternal(int minimumCapacity){
      if(minimumCapacity-value.length>0){
          value = Arrays.copyOf(value,newCapacity(minimumCapacity));
      }
  }

private int newCapacity(int minCapacity){
      int newCapacity = (value.length<<1)+2;
      if(newCapacity-minCapacity<0){
          newCapacity=minCapacity;
      }
      return (newCapacity<=0||MAX_ARRAR_SIZE-newCapacity<0)? hugeCapacity(minCapacity):newCapacity;
  }