1

我有n每个对象都有一个识别号。我让它们未排序，但索引范围(0, n-1)用于识别它们。我想尽可能快地访问它们。我想 ArrayList 将是最好的选择，我会n在 ArrayList 的位置添加带有标识符的对象，索引n为：

list.add(identifier, object);

问题是，当我添加对象时，我得到了一个，IndexOutOfBounds Exception因为我添加的对象是未排序的，并且size()较小，尽管我知道以前的位置也会被填充。

另一种选择是使用 HashMap 但我认为这会降低性能。

您知道具有上述行为的集合吗？

4

4 回答 4

2

您知道具有上述行为的集合吗？

听起来您需要一个普通的旧 Java 数组。如果你需要它作为一个集合，那么使用“Arrays.asList(...)”为其创建一个List包装器。

现在，如果您需要从数组/集合中添加或删除元素，这将不起作用，但听起来您不需要从问题描述中。

如果您确实需要添加/删除元素（与使用set更新给定位置的元素不同，那么 Peter Lawrey 的方法是最好的。

相比之下，aHashMap<Integer, Object>将是一个昂贵的选择。粗略估计，我会说“索引”操作至少会慢 10 倍，并且与等效数组或ArrayList类型相比，数据结构将占用 10 倍的空间。如果数组大且稀疏，则基于哈希表的解决方案才是真正可行的替代方案（从性能角度来看）。

于 2012-10-15T08:27:28.933 回答
1

有时，您会弄乱索引。这需要您添加稍后可能会填充的虚拟条目。

int indexToAdd = ...
E elementToAdd = ...

while(list.size() <= indexToAdd) list.add(null);
list.set(indexToAdd, elementToAdd);

这将允许您在列表的当前末尾之外添加条目。

List.add(int, E)和List.set(int, E)的 Javadoc都表示

IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index > size())

如果您尝试在末尾添加条目

List list = new ArrayList();
list.add(1, 1);

你得到

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
    at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:612)
    at java.util.ArrayList.add(ArrayList.java:426)
    at Main.main(Main.java:28)
于 2012-10-15T08:20:24.513 回答
0

HashMap<Integer, T>我不确定a会贵多少。Integer.hashCode()非常有效，尽管随着项目数量的增加，唯一真正昂贵的操作可能是将数据复制到一个新的更大的数组中。但是，如果您知道自己的n，则可以使用普通数组。

作为替代方案，您可以实现自己的Map<Integer, T>，不使用哈希码，而是使用Integer它本身。在执行此操作之前，请确保数组既不够用也HashMap不够高效！

于 2012-10-15T08:23:44.403 回答
0

我认为您至少有两个不错的选择。

第一种是使用初始化为适当长度的直接 Java 数组，然后使用以下语法添加对象：

    theArray[i] = object;

第二种是使用 HashMap，并使用以下语法添加对象：

    theMap.put(i, object);

I'm not sure what performance issues you're worried about, but adding elements within the range, clearing (out of an array) or removing (out of a HashMap), and finding elements from a given index (or key, for a HashMap) are all O(1) for both structures. I would also suggest taking a look at Wikipedia's list of data structures if neither of these seem good.

于 2012-10-15T08:34:55.970 回答