1

我正在尝试在 java 中实现一个面向列的数据存储引擎。我想知道是否有任何其他方法可以为动态增长的数组实现连续内存分配。

HashMaps 无法在扩展/调整大小时分配连续的内存块。


即使通过创建更大大小的新固定数组并将值从旧固定数组复制到这个新数组，看起来也是实现连续性的唯一选择，但与 for ex 相比，这非常慢。假设您在当前大小为 100 万的列（固定数组）中已有 100 万条记录，您需要在 1000001 位置插入新值，然后 jvm 必须创建大小为 1000001 的新数组并将所有值复制到新的更大尺寸的数组（仅插入一个值）并保持连续性。


ArrayList 在内部的工作方式与上述相同（分配新数组 + 复制旧值等）。因此，作为线程安全的具有额外同步开销的向量。


因此，通过在初始化期间创建一个巨大的固定数组来分配大量连续内存的另一种方法会导致大量未使用的内存，这不是一个可行的解决方案。


如果有更好的选择，请提供帮助。例如。类似于（如果可以在 Java 中实现）知道当前固定数组中最后一个元素的地址并以某种方式检查下一个连续可用块是否可用？如果是这样，那么使用它来存储新值以及更新数组索引以适应此新更改以维持 O(1) 时间读取访问？


谢谢。

4

2 回答 2

0

有很多技巧，但 JavaArrayList是现有的可以增长的数组的最有效组合之一。

您可以创建具有固定长度的数组，然后将它们连接到一个列表中（因此增长只需要附加一个额外的数组而不需要复制它）。但是，如果您的数据结构预计会增长很多，最好将其完全实现为列表。

您可以通过将连接的数组的大小加倍来扩展它。因此，您可以创建一个具有各自大小的数组列表，50, 100, 200, 400依此类推。您可以按如下方式计算数组（和位置）：

int x = 55; // position

int position = (int)Math.floor(Math.log(1 + x / 50) / Math.log(2));
int arrayposition = x - (Math.pow(2, position) * 50);

即使对于大数据值，这仍然是一个非常快的数据结构（O(n)数据检索和扩展的最坏情况值是O(1)）

于 2013-08-11T21:41:35.850 回答
0

如果您尝试“手动”执行此操作，则一种常见的技术是每次需要增加数组的大小时将其加倍。因此，在您的示例中，您可以将数组的大小调整为 200 万；这很昂贵，但这意味着您不需要在很长一段时间内再次调整大小。

这使您可以在摊销的常数时间内进行数组插入，尽管有时可能不希望进行昂贵的操作，例如复制 100 万行，因此您可能必须修改此想法以适应您的特定需求。有关动态数组实现的更多讨论，请参见http://en.wikipedia.org/wiki/Dynamic_array 。

于 2013-08-11T21:46:38.987 回答