Java BitSet.size()未返回构造器指定大小的问题求助

核心问题本质 #

你遇到的BitSet.size()返回64而非9的情况，是Java BitSet的设计特性导致的：它底层用long数组存储比特，每个long占64位，所以size()返回的是底层分配的总存储位数（永远是64的倍数），和你实际需要的有效比特数无关。另外BitSet.length()也帮不上忙——它只返回最高位被设为true的索引+1，完全无法识别末尾连续的有效0，比如你的测试编码000111110里最后一位是0，length()只会返回8，漏掉第9位的有效0。

对于霍夫曼编码场景，末尾的填充0会被解码逻辑当成有效编码，必然导致错误，而完全不存储有效比特长度的方案不存在，因为没有任何方式能区分“有效末尾0”和“存储填充0”，但我们可以用更节省空间的方式替代8字节的long来记录长度，或者利用霍夫曼编码特性优化。

可行解决方案 #

方案1：用更小的数值类型存储有效长度

不需要用8字节的long，根据你的压缩场景选择最小的合适类型：

• 如果单文件编码后的总比特数≤255：用byte（1字节）存储长度
• 如果≤65535：用short（2字节）
• 绝大多数文本压缩场景用int（4字节）足够，比long省一半空间

修改你的CompressedFile类，添加一个bitLength字段，转换时同步记录：

private BitSet arrayListToBitSet(ArrayList<Boolean> code, AtomicInteger bitLengthHolder) {
    int x = code.size();
    bitLengthHolder.set(x); // 把有效长度存到外部 holder 或类字段里
    BitSet bitset = new BitSet(x);
    for (int i = 0; i < x; i++) {
        bitset.set(i, code.get(i));
    }
    return bitset;
}

解码时先读取bitLength，只处理前bitLength个比特，忽略后续填充的0。

方案2：添加霍夫曼EOF终止标记

在构建霍夫曼树时，加入一个虚拟的EOF（文件结束）字符，给它分配一个唯一的前缀编码，编码完原文本后，追加这个EOF编码。解码时，一旦识别到EOF编码就停止，不需要记录总长度。

实现要点：

• 给EOF字符设置权重为0，避免影响原字符的霍夫曼树结构
• 编码时，原文本编码完成后，写入EOF的编码
• 解码时，每解析出一个字符就判断是否是EOF，是则终止解码

这种方式的额外开销只是EOF编码的比特数（通常是霍夫曼树中较长的编码，但远小于8字节），适合对空间极致敏感的场景。

方案3：自定义比特存储结构

如果不想用BitSet，可以自己实现一个轻量的比特容器，直接用byte[]存储，同时记录有效比特数：

public class HuffmanBitStore {
    private final byte[] bytes;
    private final int bitCount;

    public HuffmanBitStore(ArrayList<Boolean> code) {
        bitCount = code.size();
        // 计算需要的字节数：向上取整
        bytes = new byte[(bitCount + 7) / 8];
        
        for (int i = 0; i < bitCount; i++) {
            if (code.get(i)) {
                int byteIdx = i / 8;
                int bitPos = 7 - (i % 8); // 按高位到低位的顺序存储
                bytes[byteIdx] |= (1 << bitPos);
            }
        }
    }

    public byte[] getBytes() {
        return bytes;
    }

    public int getBitCount() {
        return bitCount;
    }

    // 解码回ArrayList<Boolean>
    public ArrayList<Boolean> toBooleanList() {
        ArrayList<Boolean> code = new ArrayList<>(bitCount);
        for (int i = 0; i < bitCount; i++) {
            int byteIdx = i / 8;
            int bitPos = 7 - (i % 8);
            boolean bit = (bytes[byteIdx] & (1 << bitPos)) != 0;
            code.add(bit);
        }
        return code;
    }
}

这种方式完全可控，没有BitSet的填充冗余，但需要自己处理比特和字节的转换逻辑。

总结 #

完全不存储有效长度的需求无法实现，但可以通过缩小长度字段的存储体积或添加EOF标记来最小化额外空间开销。其中方案1实现最简单、可靠性最高，是大多数场景的首选。

内容的提问来源于stack exchange，提问作者Laughcheeta1