What's the fastest Java collection for single threaded Contains(Point(x,y)) functionality?

Question

In my application I need to check a collection of 2D coordinates (x,y) to see if a given coordinate is in the collection, it needs to be as fast as possible and it will only be accessed from one thread. ( It's for collision checking )

Can someone give me a push in the right direction?

Answer 1

The absolute fastest I can think of would be to maintain a 2D matrix of those points:

//just once
int[][] occurrences = new int[X_MAX][Y_MAX];
for (Point p : points ) {
    occurrences[p.x][p.y]++;
}

//sometime later
if ( occurrences[x][y] != 0 ) {
    //contains Point(x, y)
}

If you don't care how many there are, just a boolean matrix would work. Clearly this would only be fast if the matrix was created just once, and maybe updated as Points are added to the collection.

In short, the basic Collections aren't perfect for this (though a HashSet would come close).

Edit

This could be easily adapted to be a Set<Point> if you don't find a library that does this for you already. Something like this:

public class PointSet implements Set<Point> {
    private final boolean[][] data; 
    public PointSet(int xSize, int ySize) {
        data = new boolean[xSize][ySize];
    }

    @Override
    public boolean add(Point e) {
         boolean hadIt = data[e.x][e.y];
         data[e.x][e.y] = true;
         return hadIt;
    }

    @Override
    public boolean contains(Object o) {
        Point p = (Point) o;
        return data[p.x][p.y];
    }

    //...other methods of Set<Point>...
}