什么是单线程Contains（Point（x，y））功能最快的Java集合？

在我的应用程序中，我需要检查2D坐标（x，y）的集合以查看给定的坐标是否在集合中，它需要尽可能快，并且只能从一个线程访问。（这是用于碰撞检查的）什么是单线程Contains（Point（x，y））功能最快的Java集合？

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

2010-06-07 Mervin

它们是整数还是浮点数？ – Jack 2010-06-07 17:13:38

绝对速度最快的我能想到的是，维持这些点的二维矩阵：

//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>，如果你不发现已经这样做了，你的图书馆。类似这样的：

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

来源

2010-06-07 17:17:06

同意：如果你不想维护整个'boolean'矩阵，'HashSet'可能是你最好的选择。 – VeeArr 2010-06-07 17:21:41

根据这个原则增加了Set的实现;请注意，您最好记下它是在哪里/是否违反集合合约。例如，这不会执行边界检查，所以如果将某个点添加到范围外，它将会失败。 – 2010-06-07 17:31:21

-1

你可以尝试某种排序集，比如treeset，因为你可以对它进行二分搜索。

来源

2010-06-07 17:23:51 Vinh

二元搜索是O（log N），而不是其他答案中给出的O（1）解。 – 2010-06-07 23:18:10

嗯，我猜你会失去速度，你可以获得空间使用和灵活性。 – Vinh 2010-06-10 21:11:39

我会去使用一些Trove collections数据结构。用于x坐标为32位，为的y坐标32位：

如果您的点存储为一对夫妇的int或几个float您可以在long收拾他们。然后你可以使用一个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值，你可以做同样的事情，但你必须打包long内的浮点数。

来源

2010-06-07 17:24:29 Jack

好的建议，尽管有一点需要注意的是你可能想要改变'TLongHashSet'使用的散列策略。默认使用'return（（int）（value ^（value >>> 32）））* 31;'这对于随机分布的数据很好，但对于这样的数据来说很糟糕。例如，像（0,1）和（1,0）这样简单的数据将导致散列冲突。对于前32位与最后32位具有相关性的多头来说，这并不好。 – 2010-06-07 19:11:37

事实上，我将'computeKey'运行在默认的散列函数中，其数据包括X和Y在0到1000之间的每个Point，并且它只产生了1024个独特的散列！这是一个99.90％的哈希碰撞概率！ – 2010-06-07 19:18:59

是的，你可能是对的。我用它来解决类似于这个问题的问题，但是它的值分布不同，所以它的工作方式就像一个魅力一样（我已经能够使编码速度提高25％，节省高达300-400 Mb的ram GB） – Jack 2010-06-07 19:51:44

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

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

如果您认为您将要对结构进行大量更新，请查看SkipList。它保证O（日志（操作））**注意这是针对所有操作，没有关于单个操作的运行时间的保证）

来源

2010-06-07 17:24:39 Jay

HashSet。它的O（1）平均值。如果你想要真正的O（1），你可以为你的对象创建一个包含对集合的引用的包装。这样，你不能只比较它与你的收藏。

来源

2010-06-07 17:25:24 takoi

什么是单线程Contains（Point（x，y））功能最快的Java集合？

回答

相关问题