TL;DR转到此处Efficient Sparse BitSet implementation in Java
我知道这是一个“老”问题，但出于同样的问题，我偶然发现了这篇文章。虽然答案很好，但我最终并不满意。经过进一步挖掘，我认为我已经找到了Java中稀疏位集问题的“确定”答案。
在this presentation中，作者布鲁斯Haddon博士讨论了他的研究人员为创建一个高内存效率和高性能的标准Java BitSet替代品所做的努力。
他的演示文稿的原始链接已经死了，但我联系了哈登博士，并保留了代码和演示文稿在这里：
https://github.com/brettwooldridge/SparseBitSet
我不能推荐阅读这篇演讲更高。它是一个迷人的阅读即使你没有兴趣稀疏位集，它更多的是关于解决问题的真正本质...
Slides: Is it Computer Science, Software Engineering, or Hacking?

如果它真的很稀疏（例如，小于1%的负载），那么使用位索引的哈希表可能是相当不错的;仅仅是索引在表中的存在或不存在是您需要知道的比特分别是1还是0的全部。
如果密度大于百分之几，则可以使用按位索引除以64进行索引的哈希表，并在包含实际位的哈希表中存储long字。如果哈希表包含 int（N/64） 的值 V 且 （V〉〉（N mod 64））&1 为真，则设置位 N。
这两个答案都假设您希望优化对位的随机访问。如果您希望优化按索引对位的顺序（或其他访问），则可能需要稀疏矩阵结构，根据预期密度使用相同类型的低级位向量表示。请参见Sparse Matrices

colt library有稀疏矩阵（1D、2D和3D），它还有一个高效的BitVector，每个值1位，而不是boolean[]那样的8位。
但是，稀疏矩阵不直接支持位，只支持双精度和对象。您可以通过将位索引Map到长索引(bitIndex>>6)（因为每个长索引包含64位）来 Package 1D稀疏双精度矩阵，将检索到的双精度转换为原始长值，并使用位操作访问检索到的长值的位。但远不及自己实现稀疏向量那么多。一旦 Package 器工作正常，您可能会避免将双精度转换为长精度，并使用双1维稀疏矩阵的可用Colt源代码作为起点实现真实的的稀疏长1维矩阵。
编辑：更多信息。Colt向量/矩阵最初不需要存储内存，假设所有位（长）最初都是0。将值设置为非零会消耗内存。将值设置回0会继续消耗内存，尽管零值的内存会定期回收。
如果这些位真的很稀疏，比如每个后备长值只有一个位设置，那么存储开销就会很低，每个实际存储位需要64位。但是正如你提到的，典型情况是20-40%稀疏，那么开销就会低得多，如果位在范围内聚集，比如位从0-100，然后是1000-1100，和2000-2200（十六进制值）。总的来说，只有1/16的区域被分配给比特，但是群集意味着比特被存储而没有浪费空间。

您可以尝试FastUtil's AVL Tree Map。

很晚才开始讨论这个问题，但是这个问题的PageRank相当高。Roaring Bitmap已经吃了很多这样的用例。

CERN COLT广泛用于向量和矩阵计算，具有稀疏矩阵，但不专门用于位向量。
http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/SparseObjectMatrix1D.html

一个散列表，仅仅是键的存在与否就能告诉你一些事情？那就是散列集了！我怀疑一个集（甚至是一个散列集）相对于位集的性能。这真的取决于速度还是内存是主要的驱动因素。

您可以尝试JavaEWAH库。
https://code.google.com/p/javaewah/
根据您的问题，它可能是一个很好的适合。
(It由Apache Hive和其他人使用。）