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

Question

在我的应用程序中，我需要检查一个二维坐标集合（x，y），以查看给定的坐标是否在集合中，它需要尽可能快，并且只会从一个线程访问。（这是为了进行碰撞检测）

有人能给我指点一下方向吗？

- Mervin

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

如果您不关心有多少个，只需要一个布尔矩阵即可。显然，如果矩阵只创建一次并且可能随着添加到集合中的点而更新，则速度会很快。

简而言之，基本的集合对于这个问题并不完美（尽管 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>...
}

- Mark Peters

---

同意：如果您不想维护整个布尔矩阵，那么使用 HashSet 可能是最好的选择。 - VeeArr

根据这个原则，添加了一个基于Set的实现；请注意最好记录它何时/是否违反Set契约。例如，这不会进行边界检查，因此如果您添加超出范围的Point，则会失败。 - Mark Peters

Answer 2

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

如果您的点被存储为一对int或一对float，您可以将它们打包在一个long中：32位用于x坐标，32位用于y坐标。然后，您可以使用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(..);

如果您有浮点数值，您也可以做同样的事情，但是您必须将浮点位打包到长整型内部。

- Jack

---

好的建议，不过需要注意的一点是您可能想要更改 TLongHashSet 使用的哈希策略。默认使用 return ((int)(value ^ (value >>> 32))) * 31;，这对于随机分布的数据很好，但对于像这样的数据则很糟糕。例如，像 (0,1) 和 (1,0) 这样简单的数据将导致哈希冲突。对于长整型而言，第一个32位与最后32位有相关性的情况也不适用。 - Mark Peters

事实上，我在包括所有X和Y在0到1000之间的点的数据的默认哈希函数上运行了您的“computeKey”，它只生成了1024个唯一的哈希值！这是99.90％的哈希碰撞概率！！ - Mark Peters

是的，可能你说得对。我用它来解决了一个类似但值分配不同的问题，所以它非常顺利（我成功地编写出了比以前快25%的代码，并且节省了2.0 Gb中高达300-400 Mb的内存）。 - Jack

Answer 3

HashSet。它的平均时间复杂度为O(1)。如果你想要真正的O(1)，你可以为你的对象创建一个包装器，该包装器具有对集合的引用。这样你就不能仅仅将它与你拥有的集合进行比较。

- gwohpq9

Answer 4

相对于搜索，您需要多频繁地更新集合？您应该根据此选择适当的数据结构。

Point2D实现了可比性，对吧？那么您最好选择TreeSet，它们非常快速，我相信它们依赖于B+树，您可能知道它们用于实际数据库和文件系统。

如果您认为您将会对结构进行相当数量的更新，请查看SkipList。它保证O(log(operations)) **请注意，这是您执行的所有操作，没有关于单个操作的运行时间的保证）

- Jay

Answer 5

你可以尝试使用一些排序集合，比如TreeSet，因为你可以在其中进行二分查找。

- Vinh

---

二分查找的时间复杂度为O(log N)，而其他答案中给出的解决方案为O(1)。 - Kevin Bourrillion

好吧，我想你在速度上失去的，可以通过空间使用和灵活性来获得。 - Vinh