Java为动态增长的数组连续分配内存？

Question

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

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

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

ArrayList 的内部工作方式与上述相同(分配新数组 + 复制旧值等)。因此，作为 vector ，需要额外的同步开销来保证线程安全。

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

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

谢谢。

Answer 1

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

这可以让您在摊销恒定时间内进行数组插入，尽管偶尔进行昂贵的操作(例如复制 100 万行)可能是不受欢迎的，因此您可能必须修改此想法以满足您的特定需求。请参阅http://en.wikipedia.org/wiki/Dynamic_array有关动态数组实现的更多讨论。