单线程包含(Point(x,y))功能的最快Java集合是什么？

Question

在我的应用程序中,我需要检查2D坐标(x,y)的集合,以查看给定坐标是否在集合中,它需要尽可能快,并且只能从一个线程访问.(这是用于碰撞检查)

有人能给我一个正确的方向吗？

Answer 1

我能想到的绝对最快的是维持这些点的二维矩阵:

//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)
}

如果你不关心有多少,只需一个boolean矩阵即可.显然,如果矩阵只创建一次,这种情况就会很快,并且可能会在将点添加到集合中时更新.

简而言之,基本的集合并不是完美的(尽管HashSet很接近).

编辑

Set<Point>如果您找不到已经为您执行此操作的库,则可以轻松地将其调整为a .像这样的东西:

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>...
}