Java数据结构之位图的简单实现和使用

public static class BitMap {
    private final long[] bits;

    // 位图初始化
    public BitMap(int max) {
    }

    // 添加一个元素
    public void add(int num) {
    }

    // 删除一个元素
    public void remove(int num) {
    }

    // 判断一个元素是否在位图中
    public boolean contains(int num) {
    }
}

public void add(int num) {
    bits[num / 64] |= (1L << (num % 64));
}

// 向位图中添加值, 将对应的二进制位改成1即可
public void add(int num) {
    // 1. num / 64 找到该数应该存在数组的哪个元素上
    // 2. num % 64 找到该数应该存到元素的第几个二进制位置上(从0位置开始)
    // 3. ( 1L << (num % 64) ) | bits[num / 64] 就是将相应二进制位的值修改为1, 不影响其他位
    // 要注意1后面必须加上L, 1默认是一个int类型的数, 是没有64位的, 移位运算就可能会出错
    //  num / 64       1L << (num % 64)
    bits[num >> 6] |= (1L << (num & 63));
}

~(1L << (num & 63));

// 在集合中删除记录, 将对应二进制位改成0即可
public void remove(int num) {
    // 1. num / 64 找到该数应该存在数组的哪个元素上
    // 2. num % 64 找到该数应该存到元素的第几个二进制位置上(从0位置开始)
    // 3. ~( 1L << (num % 64) ) 就是在把0001000变成1110111这样的
    // 4. 把 3 得到的结果再 & 到 bits[num >> 6] 就行了
    bits[num >> 6] &= ~(1L << (num & 63));
}

public boolean contains(int num) {
    return (bits[num >> 6] & (1L << (num & 63))) != 0;
}

// 位图的简单实现
public class BitMap {
    private long[] bits;
    // 传入集合要保存的最大数值
    public BitMap(int max) {
                           // max / 64 + 1
        this.bits = new long[(max >> 6) + 1];
    }
    // 向位图中添加值, 将对应的二进制位改成1即可
    public void add(int num) {
        // 1. num / 64 找到该数应该存在数组的哪个元素上
        // 2. num % 64 找到该数应该存到元素的第几个二进制位置上(从0位置开始)
        // 3. ( 1L << (num % 64) ) | bits[num / 64] 就是将相应二进制位的值修改为1, 不影响其他位
        // 要注意1后面必须加上L, 1默认是一个int类型的数, 是没有64位的, 移位运算就可能会出错
        //  num / 64       1L << (num % 64)
        bits[num >> 6] |= (1L << (num & 63));
    }
    // 在集合中删除记录, 将对应二进制位改成0即可
    public void remove(int num) {
        // 1. num / 64 找到该数应该存在数组的哪个元素上
        // 2. num % 64 找到该数应该存到元素的第几个二进制位置上(从0位置开始)
        // 3. ~( 1L << (num % 64) ) 就是在把0001000变成1110111这样的
        // 4. 把 3 得到的结果再 & 到 bits[num >> 6] 就行了
        bits[num >> 6] &= ~(1L << (num & 63));
    }
    // 查看位图中是否记录了某个值
    public boolean contains(int num) {
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }
}

import java.util.HashSet;
public class BitMap {
    private long[] bits;
    public BitMap(int max) {
        bits = new long[(max + 64) >> 6];
    }
    public void add(int num) {
        bits[num >> 6] |= (1L << (num & 63));
    }
    public void remove(int num) {
        bits[num >> 6] &= ~(1L << (num & 63));
    }
    public static void main(String[] args) {
        System.out.println("测试开始!");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTime = 10000000;
        for (int i = 0; i < testTime; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.333) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {
                bitMap.remove(num);
                set.remove(num);
            } else {
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("出错了!");
                    break;
                }
            }
        }
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("出错了!");
            }
        }
        System.out.println("测试结束!");
    }
}