java数据结构之位图运算

方法一：自定义BitMap

代码如下：

    static class BitMap {

        //存储数据的数组，每个元素表示 64 位的数据
        private final long[] bits;

        //构造函数，初始化 bits 数组
        public BitMap(int size) {
            bits = new long[size / 64 + 1];
        }

        //添加一个数字到数组中
        public void add(int num) {
            int index = (num / 64);
            int offset = (num % 64);
            bits[index] |= (1L << offset);
        }

        //从数组中删除一个数字
        public void remove(int num) {
            int index = (num / 64);
            int offset = (num % 64);
            bits[index] &= ~(1L << offset);
        }

        //判断数组中是否包含某个数字
        public boolean contains(int num) {
            int index = (num / 64);
            int offset = (num % 64);
            return (bits[index] & (1L << offset)) != 0;
        }

        //获取数组中所有数字的集合
        public List<Integer> getNumbers() {
            List<Integer> numbers = new ArrayList<>();
            for (int i = 0; i < bits.length; i++) {
                long bit = bits[i];
                for (int j = 0; j < 64; j++) {
                    if ((bit & (1L << j)) != 0) {
                        numbers.add(i * 64 + j);
                    }
                }
            }
            return numbers;
        }
    }

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(Integer.MAX_VALUE);
        bitMap.add(99);
        bitMap.add(100);
        bitMap.add(101);
        bitMap.add(100);
        System.out.println("是否包含99？ " + bitMap.contains(99));
        System.out.println("是否包含98？ " + bitMap.contains(98));
        bitMap.remove(99);
        System.out.println("是否包含99？ " + bitMap.contains(99));
        System.out.println("打印已存数据：" + bitMap.getNumbers());
    }
    

执行结果：

是否包含99？ true
是否包含98？ false
是否包含99？ false
打印已存数据：[100, 101]

Process finished with exit code 0

方法二：使用java类BitSet

代码如下：

    public static void main(String[] args) throws Exception {
        // 创建一个 BitSet 对象，用于存储数字
        BitSet bitSet = new BitSet();
        bitSet.set(99);
        bitSet.set(100);
        bitSet.set(101);
        bitSet.set(100);
        System.out.println("是否包含99？ " + bitSet.get(99));
        System.out.println("是否包含98？ " + bitSet.get(98));
        bitSet.clear(99);
        System.out.println("是否包含99？ " + bitSet.get(99));
        //打印出所有数据
        System.out.println("打印已存数据：" + bitSet);
    }

执行结果：

是否包含99？ true
是否包含98？ false
是否包含99？ false
打印已存数据：{100, 101}

Process finished with exit code 0

总体来说，位图是一种非常高效的数据结构，它可以用来存储和查找大量的数据。但是，位图的数据类型单一，数据访问不灵活，因此在使用时需要注意这些缺点。