单线程 Contains(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)
}

如果您不关心有多少个点，那么只需一个布尔矩阵就可以了。显然，只有在矩阵仅创建一次并且可能在将点添加到集合中时进行更新时，这才会很快。

简而言之，基本的 Collections 对此并不完美（尽管 HashSet 会很接近）。

编辑

如果您还没有找到可以为您执行此操作的库，则可以轻松将其改编为Set。像这样的事情：

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

Answer 2

我会使用一些 Trove 集合 数据结构。

如果您的点存储为几个 int 或几个 float，您可以将它们打包在 long 中：x 坐标为 32 位y 坐标为 32 位。然后，您可以使用 TLongHashSet，它是针对原始数据进行优化的 HashSet（与普通 Java 集合相比，它速度更快，消耗的内存更少）。

如果你有 int 坐标，那么就像

static private long computeKey(int h1, int h2)
{           
    return ((long)h1) << 32 | h2;
}

计算密钥然后使用它，

TLongHashSet set = new TLongHashSet()
set.add(long v);
set.addAll(long[] v);
set.containsAll(..);

如果你有 float 值，你可以做同样的事情，但你必须打包 float long 内的位。

Answer 3

哈希集。其平均值为 O(1)。如果您想要真正的 O(1)，您可以为您的对象创建一个包装器，该对象具有对集合的引用。这样你就不能仅仅将它与你拥有的收藏进行比较。

Answer 4

与搜索集合相比，您需要多久更新一次集合？您应该基于此选择合适的数据结构。

Point2D 实现类似，对吗？那么你最好的选择可能是 TreeSet，它们的速度非常快，而且我相信它们依赖于 B+ 树，你可能知道 B+ 树在实际的数据库和文件系统中使用。

如果您认为要对结构进行大量更新，请查看 SkipList。它保证 O(log(operations)) **注意，这适用于您执行的所有操作，不保证单个操作的运行时间）

Answer 5

您可以尝试某种排序集，例如树集，因为您可以对其进行二分搜索。