1

我想在 java 中创建一个哈希表类，我将键、值对存储在链接列表的 ArrayList 中。我通过声明来做到这一点

 ArrayList<LinkedList<T>> storage = new ArrayList();

然后我想创建一个linkList 对象，然后我可以使用它在arrayList 的每个索引内创建一个新的链表。我通过声明来做到这一点：

  LinkedList<T> list = new LinkedList<T>();

然后我将我的添加函数设置为将元素添加到数组列表的哈希键索引内的 LinkedList 的第一个索引，如下所示：

public void add(K key, T value){    
int arrayListIndex = (key.hashCode()) % this.initialCapacity;
    System.out.println(arrayListIndex); //This tells us where we access the Array List;


    if (hashBrown.get(arrayListIndex) == null){

        hashBrown.add(arrayListIndex, list);
        hashBrown.get(arrayListIndex).addFirst(value);
    }
}

每次运行此代码时，我都会收到一个错误，其中我的索引为 7，我的大小为 0。这会导致错误：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 7, Size: 0
    at java.util.ArrayList.rangeCheck(ArrayList.java:571)
    at java.util.ArrayList.get(ArrayList.java:349)
    at FastHashtable.add(FastHashtable.java:72)
    at FastHashtable.main(FastHashtable.java:145)

我无法追踪这个索引越界错误的来源，任何人都可以提供建议。我在使用 ArrayLists 方面相当陌生，这让我认为我对 arrayList 的原始声明是不正确的。

4

2 回答 2

4

您将容量与大小混淆了ArrayList。从 Oracle Java 文档：

每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它总是至少与列表大小一样大。随着元素被添加到 中ArrayList，它的容量会自动增长。除了添加一个元素具有恒定的摊销时间成本这一事实之外，没有指定增长策略的细节。

相反，您应该考虑创建一个普通数组（例如Object[] a = new Object[maxSize]），您可以在其中实际分配任意索引值的对象（在这种情况下为链表）。如果您只想存储链表，请创建一个LinkedList<T>[]数组。

于 2012-11-10T22:51:55.297 回答
3

如果列表中有 0 个元素，则无法添加到索引 7 处的列表。您只能在末尾添加（使用add没有索引的方法）或在不大于当前列表的size().

当列表为空并且您在索引 7 处添加一些内容时，您希望列表在第一个位置包含什么，以及在索引 6 处包含什么？null（我曾经创建了一个 list 的子类，以在添加索引大于列表大小时将所有内容填充到索引中，但这种行为不够普遍，无法成为List's 语义的一部分。

[编辑以回应此处的评论和 praseodym 的回答]

当第一次访问相应的位置时，您可以简单地用空值填充（数组）列表，用链表替换那些。（但请务必使用setand not add，这可能也是您在上面想要的。）或者，您可以创建一个所需大小的数组（null默认情况下将充满 s ）并将其“包装”成 (不可调整大小）列表通过Arrays.asList。但是，您必须忽略“未经检查的转换”警告（并不是说您可以在使用数组时避免警告）。另外，我建议您阅读“ Program to an interface, not an implementation ”。

于 2012-11-10T22:48:39.233 回答