在Java中创建动态数组而不使用集合

Question

在Java中创建动态数组而不使用集合

javaarrays

4

我在面试中被问道："如何创建一个动态数组而不使用任何集合，例如ArrayList、Vector等。"

我回答说这不可能，因为数组是固定大小的。他们说可以，你需要编写一个程序来回答这个问题。

我无法回答这个问题。他们给了我一个提示"使用泛型"，尽管对我来说回答这个问题似乎非常困难。有人能帮帮我吗？

- Mehak Batra

3

也许他们只是想让你自己编写一个 ArrayList 的实现。谁知道呢，我们肯定不知道。 - Kayaman

这绝对是可能的。事实上，这就是Java集合框架的实现方式。其思想是创建一个类，将List<T>接口放在内置的、不可调整大小的数组包装的实现之上。查看ArrayList<T>的源代码以了解其实现方式。 - Sergey Kalinichenko

4个回答

0

我对你的问题有一些想法。动态数组是在运行时更改大小的东西。我刚刚完成了十二年级，现在分享我脑海中的想法...

程序：

public class DynamicArr {//method to increase size dynamically during runtime

    public static int[] incrSize(int arr[]) {
        int len = arr.length;
        int newArr[] = new int[len+1]; //increasing the length of the current array in an other temporary array
        return newArr; // returning the new array

    }

    public static void main(String... strings) {
        int a[] = new int[10];
        System.out.println("Size Before Increase: " + a.length);
        a = incrSize(a); // pointing the reference to the new array by calling the incrSize() method
        System.out.println("Size After Increase: " + a.length);

    }

}

您可以将当前数组中的所有值复制到临时数组中，并将新值添加到可以扩展数组大小的数组中。您也可以根据需要扩展大小。

希望这可以帮助到您...

- Ishwar

0

他们基本上想了解一些事情。例如，您如何为这样的数组建模“Holder”，您如何公开使用get（int index）或set（T value，int index）或size。

“使用泛型”是一个非常好的提示，因为您至少应该从以下内容开始：

Holder<T> {
   T[] array = (T[])new Object[10]; // 10 just as an example  
}

如果你把这个写下来，他们可能会进一步问为什么不用T[] array = new T[10]，你应该说在Java中不能创建泛型数组（你甚至可以在这里提到@SafeVarArgs）。接着你应该说数组是协变的，强制转换对于数组是允许的，但对于集合不行；此外，它会生成一个编译器警告，需要你去抑制。

之后你可以添加一个方法，比如add(T value)，并说明如何实现。在这里，他们希望你知道Arrays.copyOfRange或System.arrayCopy是什么以及它们的工作原理。

他们甚至可能会问为什么不添加所有的T子类型以及正确的语法（查找泛型边界）。

这也需要您考虑如何在特定索引上删除元素？您会将其 null 吗？还是直接删除？如果是，从数组中如何删除？当某些内容被删除时，您会缩小数组的大小吗？（提示：Java 集合不会这样做，除非您明确告诉它们：ArrayList#trimToSize()）

当您的内部数组已满，并且您想要添加一个元素时，您会扩展多少？50%、75%？还是只有足够容纳单个元素的空间？如果您知道 jdk 的内部集合如何工作，答案就很简单。

我认为这并不是一个坏的面试问题。

- Eugene

0

Java中的动态数组是什么？以下是一个概念性的例子：我们想要在数组中存储数据，但我们不知道它有多大。因此，当我们想要插入数据时，如果没有足够的空间，我们需要找到一个更大的内存块，并复制该块中的所有条目。现在考虑两种方法。
不好的方法
我们分配了一个1000个条目的块。
每次没有足够的空间时，我们都会分配一个新的块，其中包含100个以上的条目。
这需要多长时间：
要插入n个条目，复制的次数将为1000 × k + 100 × (1 + 2 + . . . + ( k − 1)) = 1000 k + 50k(k−1) 因此，所需的时间与k和n的平方成正比。
好的方法
分配一个1000个条目的块，当没有足够的空间时，分配一个两倍大小的新块。
这需要多长时间
总复制次数为：1000 × (1 + 2 + 4 + ··· + 2^( k − 1) ) = 1000 × (2^k − 1) <= n
总插入次数为：1000 × (1 + 1 + 2 + 4 + ··· + 2^( k − 1) ) = 1000 × 2^k=n
因此，总时间与n成线性关系，平均时间是恒定的。
一旦您理解了这个概念，您就能够在任何您熟悉的语言中创建动态数组。

- Moe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Saurabh Singh · Accepted Answer

集合的实现使用类似的概念。您需要定义一个默认大小为n = 10（比如说）和默认负载因子为0.75（比如说）的通用数组。

T[] array = (T[])new Object[DEFAULT_SIZE];

需要一个变量index来存储数组中的当前位置。

当 index > n*load_factor 时，创建一个更大的新数组，并将所有元素复制到新数组中，这将成为您的新数组。同样地，当删除元素时，index < n*load_factor (这些标准取决于许多参数，这只是一个例子)，需要缩小数组的大小。

部分示例代码：

public class CustomArrayList <T> {
  private int index = 0;
  private final int DEFAULT_SIZE = 10;
  private final double DEFAULT_LOAD = 0.75;
  private T[] array;

  public CustomArrayList(){
    array = (T[])new Object[DEFAULT_SIZE];
  }

  public void add(T elem){
    if(index>=array.length*DEFAULT_LOAD){
        array = Arrays.copyOf(array, array.length+10);
    }
    array[index++]=elem;
  }
}