3

我们有一个有趣的挑战。我们必须控制对驻留在“bins”中的数据的访问。可能会有数十万个“垃圾箱”。对每个垃圾箱的访问都是单独控制的，但这些限制可以而且可能会重叠。我们正在考虑在位掩码（1、2、3、4 等）中为每个 bin 分配一个位置。

然后，当用户登录系统时，我们会查看他的安全属性并确定允许他查看哪些 bin。使用该信息，我们为该用户构建了一个位掩码，其中“设置”位对应于他允许查看的 bin 的标识符。因此，如果他可以看到 bin 1、3 和 4，他的位掩码将是 1101。

因此，当用户搜索数据时，我们可以查看返回行的 bin 索引，看看该位是否设置在他的位掩码上。如果他的位掩码设置了该位，我们让他看到该行。我们计划将位掩码存储为BigIntegerJava 中的 a。

我的问题是：假设索引号没有变得比 Integer.MAX_INT 大，那么BigInteger位掩码是否会扩展到数十万位位置？BigInteger.isBitSet(n)在 n 可能很大的地方（例如 874,837）需要永远运行吗？创造这样的作品需要永远BigInteger吗？

其次：如果您有其他方法，我很想听听。

4

4 回答 4

4

如果您不经常更改 BigInteger 应该很快。

更明显的选择是专为此类事情设计的BitSet 。对于查找位，我怀疑性能是相似的。对于创建/修改，使用 BitSet 会更有效。

注意：PaulG 评论说差异是“令人印象深刻的”并且 BitSet 更快。

于 2012-09-19T15:57:20.443 回答
2

Java 有一个更方便的类，称为BitSet.

您不需要检查该位是否在循环中设置：您可以制作一个掩码，使用按位and，并查看结果是否为非空来决定是授予还是拒绝访问：

BitSet resourceAccessMask = ...
BitSet userAllowedAccessMask = ...
BitSet test = (BitSet)resourceAccessMask.clone();
test.and(userAllowedAccessMask);
if (!test.isEmpty()) {
    System.out.println("access granted");
} else {
    System.out.println("access denied");
}

我们在我以前的公司的类似情况下使用过这个类，并且性能对于我们的目的来说是可以接受的。

于 2012-09-19T15:58:02.850 回答
1

您可以为此定义自己的 Java 接口，最初使用 JavaBitSet来实现该接口。

如果您遇到性能问题，或者您需要在很久以后使用，您可以始终提供不同的实现（例如，使用缓存或类似改进的实现）而不更改其余代码。仔细考虑您需要的接口，并选择一个long索引以确保您可以随时检查它是否在稍后的实现中超出范围（或最初简单地返回“无访问权”）任何东西index > Integer.MAX_VALUE。

使用BigInteger不是一个好主意，因为该类不是为特定目的而编写的，更改它的唯一方法是创建一个全新的副本。它在内存使用方面很有效；它在内部使用一个由 64 位长组成的数组（目前，这当然可以改变）。

于 2012-09-19T16:14:40.187 回答
0

值得考虑的一件事（除了使用 BitSet）是使用不同的粒度。因此，您使用较短的位集，其中每个位“保护”多个实际位。这样，您就不需要在 ram 中为每个用户提供数百万位。

实现此目的的一种简单方法是设置较小的位，例如 n/32 并执行以下操作：

boolean isSet(int n) {
    return guardingBits.isSet(n / 32) && realBits.isSet(n);
}

如果这些位大多为零，这为您提供了避免加载实际位的好机会。您可以修改此方法以匹配预期的位集。如果您希望几乎所有位都已设置，则可以使用此保护位来存储一个，如果它保护的所有位都已设置。因此，您只需要检查可能为零的位。

这甚至可能是一个开始。根据使用情况和要求，您可能希望使用 B-tree 或分页版本，其中您只在内存中保存一小部分大位字段。

于 2013-12-09T22:26:23.153 回答