ArrayList索引超出范围,但HashSet没有问题。

huangapple go评论67阅读模式
英文:

ArrayList index out of bound but HashSet has no issue

问题

我有一个简单的Graph类,它使用一个List数组来跟踪哪些元素彼此链接。

在从列表中删除元素时,我遇到了IndexOutOfBoundsException错误。我的错误信息在代码下方。

但是,如果我将集合从ArrayList<Integer>更改为HashSet<Integer>,那么它就能正常工作。

为什么Arraylist<Integer>类型不起作用,但HastSet<Integer>可以工作?

这些集合的内部元素移除机制是什么?

class Graph {
    int v;
    ArrayList<Integer>[] connections;

    Graph(int v) {
        this.v = v;
        connections = new ArrayList[v];
        for (int i = 0; i < v; i++) {
            connections[i] = new ArrayList<>();
        }
    }

    void addConnection(int u, int v) {
        connections[u].add(v);
        connections[v].add(u);
    }

    void removeConnection(int u, int v) {
        connections[u].remove(v);
        connections[v].remove(u);
    }
}

class Main {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> result = new ArrayList<>();
        Graph graph = new Graph(n);

        for (List<Integer> connection : connections) {
            graph.addConnection(connection.get(0), connection.get(1));
        }

        for (List<Integer> connection : connections) {
            graph.removeConnection(connection.get(0), connection.get(1));
            graph.addConnection(connection.get(0), connection.get(1));
        }
    }
}

异常信息:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
at java.base/java.util.Objects.checkIndex(Objects.java:372)
英文:

I have a simple Graph class, which tracks which elements are linked to eachother using an array of Lists.

I am getting IndexOutOfBoundsException when removing an element from the list. My error is given below the code.

But if I change the collection from ArrayList<Integer> to HashSet<Integer>, it works fine.

Why does Arraylist<Integer> type not work here but HastSet<Integer> works?

And what is the internal mechanism of removing elements of these collections?

class Graph {
int v;
ArrayList<Integer>[] connections;
Graph(int v) {
this.v = v;
connections = new ArrayList[v];
for (int i = 0; i < v; i++) {
connections[i] = new ArrayList<>();
}
}
void addConnection(int u, int v) {
connections[u].add(v);
connections[v].add(u);
}
void removeConnection(int u, int v) {
connections[u].remove(v);
connections[v].remove(u);
}
}
class Main{
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
List<List<Integer>> result = new ArrayList<>();
Graph graph = new Graph(n);
for (List<Integer> connection : connections) {
graph.addConnection(connection.get(0), 
connection.get(1));
for (List<Integer> connection : connections) {
graph.removeConnection(connection.get(0), 
connection.get(1));
graph.addConnection(connection.get(0), 
connection.get(1));
}
}

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
at java.base/java.util.Objects.checkIndex(Objects.java:372)

答案1

得分: 2

您的问题是方法签名:

void removeConnection(int u, int v) { // <-- These should be Integer, not int
    connections[u].remove(v);
    connections[v].remove(u);
}

问题在于 List两个 remove 方法:

  1. remove(int index) 用于移除索引为 index 的元素
  2. remove(Object object) 用于查找并移除 object

而您正在调用版本 1,但您想要版本 2。

然而,Set 没有 remove(int index) 方法,所以 Java 会自动将 int 转换为 Integer,然后方法才按预期工作(正如您所发现的)。

通过将方法签名更改为:

void removeConnection(Integer u, Integer v)

将调用正确版本的 remove()。如果将一个 int 传递给该方法,它将被自动装箱为 Integer,因此您对该方法的使用无需更改。


这种情况是一个特殊情况;它仅在集合类型为 Integer 尝试自动装箱时才会发生。然而,它发生的频率足够高,以至于这个特殊情况值得记在脑后,因为它可能会让人困惑,即使进行仔细调试也很难发现。

英文:

Your problem is the method signature:

void removeConnection(int u, int v) { // <-- These should be Integer, not int
connections[u].remove(v);
connections[v].remove(u);
}

The reason is List has two remove methods:

  1. remove(int index) that removes the element at index index
  2. remove(Object object) that finds and removes object

and you are calling version 1, but you want version 2.

Set however does not have the remove(int index) method, so java auto-boxes the int to an Integer and the method works as intended (as you discovered).

By changing the method signature to

void removeConnection(Integer u, Integer v)

the correct version of remove() is called. If an int is passed to the method, it will be auto-boxed to an Integer, so your usage of this method does not need to change.


This is situation is a corner case; it only occurs when the collection type is Integer and when autoboxing is being attempted. However, it comes up often enough that this special case is worth keeping in the back of your mind, due to the puzzlement and it's hard to pick up even if carefully debugging.

huangapple
  • 本文由 发表于 2020年8月11日 05:24:00
  • 转载请务必保留本文链接:https://go.coder-hub.com/63348233.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定