时间戳

首页 > 解决方案 > 为什么 Java 的 BitSet 内部存储长数组，而 set 方法使用 int？

java - 为什么 Java 的 BitSet 内部存储长数组，而 set 方法使用 int？

问题描述

根据BitSet实现，它在内部使用了一个 long 数组：

/**
 * The internal field corresponding to the serialField "bits".
 */
private long[] words;

但是对于set它使用int的方法：

public void set(int bitIndex) {...}

所以基本上我们可以存储(2^31 - 1) * 64 * 8 = 2,147,483,642 * 64 * 8 = 137,438,953,088 bits，但是使用int索引我们只能访问第一位2,147,483,648。

这意味着137,438,953,088 - 2,147,483,648 = 135,291,469,440位不可用。

但是如果这个类的开发人员使用long而不是int用于位索引，它将解决所有问题，因为long我们可以导航低谷2^63 - 1 = 9,223,372,036,854,775,807 bits

即使从性能的角度来看，它也没有任何意义。

int使用而不是long索引和丢失数十亿位的逻辑背后的原因是什么？

PS One 可以说问题2 GiB出在堆大小上，但今天它不再是问题了。

标签： javabitlong-integerbitset

解决方案

国家的文件java.util.BitSet：

a 的位BitSet由非负整数索引。

这是它应该做的，所以不需要long索引。

它的内部数据结构可以支持超过 2^31 个单独的位，这是一个与类的公共接口无关的实现细节（他们可以使用boolean[]数组并且类仍然可以工作，尽管内存占用更大，并且某些方法的运行时间更长。）

问题仍然存在：这个类的公共接口会改变以支持long索引吗？

这是极不可能的，因为支持long索引意味着像这样的方法

  • int cardinality()
  • int nextClearBit()（和类似的方法：下一个/上一个清除/设置位）
  • int size()
  • IntStream stream()

还需要更改，这会破坏现有代码。

我能想到具有索引的BitSet类似类的唯一方法是增加一个类（或任何你喜欢的类），以便需要超过 2^31 位的位集的人可以切换到那个新类。longBigBitSetLongBitSet

这样的类是否会被添加到java.util包中是另一个问题——因为你必须让 JCP 执行委员会相信这是当前 Java 生态系统中一个重要的补充/漏洞。

推荐阅读