java - ArrayList 的访问速度更快的版本？

Question

有人知道类似于 ArrayList 的东西，它更适合尽快处理大量数据吗？

我有一个带有非常大的 ArrayList 的程序，当它尝试探索或修改 ArrayList 时，它会被阻塞。

大概当你这样做时:

//i is an int;
arrayList.remove(i);

幕后代码运行如下:

public T remove(int i){
    //Let's say ArrayList stores it's data in a T [] array called "contents".
    T output = contents[i];
    T [] overwrite = new T [contents.length - 1];
    //Yes, I know generic arrays aren't created this simply. Bear with me here...
    for(int x=0;x<i;x++){
        overwrite[x] = contents[x];
    }
    for(int x=i+1;x<contents.length;x++){
        overwrite[x-1] = contents[x];
    }
    contents = overwrite;
    return output;
}

当 ArrayList 的大小为几百万个单位左右时，重新排列数组中项目位置的所有这些循环将花费大量时间。

我尝试通过创建自己的自定义 ArrayList 子类来缓解此问题，该子类将数据存储分段为更小的 ArrayList。任何需要 ArrayList 扫描其数据以查找特定项目的进程都会为其中每个较小的 ArrayList 生成一个新的搜索线程(以利用我的多个 CPU 核心)。

但是这个系统不起作用，因为当调用搜索的线程在任何 ArrayList 中同步有一个项目时，它可以阻止那些单独的搜索线程完成搜索，从而锁定调用该搜索的原始线程。在这个过程中进行搜索，基本上使整个程序陷入僵局。

我确实需要某种数据存储类，能够像 PC 一样快速地包含和操作大量对象。

有什么想法吗？

Answer 1

I really need some kind of data storage class oriented to containing and manipulating large amounts of objects as quickly as the PC is capable.

答案很大程度上取决于您所讨论的数据类型以及您需要的具体操作。您使用“探索”这个作品而不对其进行定义。

如果您正在谈论查找记录，那么没有什么比用于线程操作的 HashMap - ConcurrentHashMap 更好了。如果您正在谈论保持顺序，尤其是在处理线程时，那么我建议使用 ConcurrentSkipListMap ，它具有 O(logN) 查找、插入、删除等功能。

您可能还想考虑使用多个集合。您需要注意集合不要不同步，这对于线程来说尤其具有挑战性，但根据您正在进行的各种操作，这可能会更快。

When the size of the ArrayList is a couple million units or so, all those cycles rearranging the positions of items in the array would take a lot of time.

如上所述，ConcurrentSkipListMap 重新排列项目的时间复杂度为 O(logN)。即删除并添加新位置。

The [ArrayList.remove(i)] code behind the scenes runs something like: ...

其实不是。你可以看看code in the JDK正确的？ ArrayList 使用 System.arraycopy(...) 进行此类操作。它们对于您的情况可能效率不高，但它不是 O(N)。