In the last chapter, we talked about how BitMap stores data. If you haven’t seen it, you can see the BitMap algorithm

This article we will talk about BitMap this data structure code implementation.

Let’s review how data is stored

A binary bit corresponds to a non-negative n, which has the value 1 if it exists and 0 otherwise.

At this point, our first question:

We are using byte,int,short,long and other data types when storing data, they all take up at least one byte of memory, that is, 8 bits, that is to say, the smallest operation unit is 8 bits. There is no such thing as a bit-by-bit data type.

In the Java bitMaP implementation, it uses a long data to store. A long takes up eight bytes, or 64bit, so a long can store 64 numbers. For example, if ARR is an array of type long, arR [0] can store 0 to 63, arr[1] can store 64 to 127, and so on.

But let’s use byte arrays to store it. A byte occupies one byte, that is, eight bits, which can hold eight digits.

Of course, if you want to store it in a long array, you can. It’s the same thing in terms of implementation.

For example, when we want to store (1,3,5,7,8,10), their memory would look like this.

Now let’s talk about how to operate one bit at a time.

How do I add a value to a bitmap

Let’s talk about how to add a value to a bitmap. For example, we want to add n=14.

So this is actually pretty simple, so let’s find the index of n in arR array, index is 1. Position = 6 in arr[index]

It’s still pretty easy to figure out the formula for index and position. namely

Index = n / 8 = N >> 3.

Position = n % 8 = n & 0x07.

Move 1 to the right of position and perform the “or” operation with arr[index]. The following figure

One important thing to note here is that in drawing, for convenience, we use the left bit as the low bit and the right bit as the high bit. But in actual storage, the one on the left saves the high and the one on the right saves the low. So in our code implementation, what we call a right shift corresponds to a left shift in our code.

Code implementation

// Add data operation

public void add(int n){
    // The operation with >> is faster
    int index = n >> 3;
    int position = n & 0x07;
    // Move 1 to the right and do the or
    << corresponds to the right shift in the figure above. In fact, << is the left shift.
    arr[index] |= 1 << position;
}
Copy the code

Given the Add operation, the other operations are pretty much the same.

Of course, the add operation we implemented is just a simple implementation, if you want to implement rigorously, still need a lot of exception judgment. For example, check whether the number is non-negative, check whether the arR array subscript is out of bounds, expand the capacity, and so on. If you are interested, you can implement it carefully.

Delete operation.

We just need to change the corresponding binary 1 to 0.

We can invert the result of a right shift of 1, and then do the and operation with arr[index]. The code is as follows:

public void delete(int n){
    int index = n >> 3;
    int position = n & 0x07;
    arr[index] &= ~(1 << position);
}
Copy the code

Determines whether an operation exists

If arr[index] is not 0, then it does not exist. If arr[index] is not 0, then it does not exist.

public boolean contain(int n){
    int index = n >> 3;
    int position = n & 0x07;
    return (arr[index] & (1<< position)) ! =0;
}

Copy the code

The three most basic operation code is basically implemented.

I hope you can go to practice.

Full code:

public class BitMap {
    private byte[] arr;
    // Capacity, that is, the maximum number of data can be stored
    private int capacity;

    public BitMap(int capacity) {
        this.capacity = capacity;
        // A byte can hold 8 bytes. Capacity actually refers to the number of bits
        arr = new byte[(capacity / 8 + 1)];
    }

    // Add data operation

    public void add(int n){
        // The operation with >> is faster
        int index = n >> 3;
        int position = n & 0x07;
        // Move 1 to the right and do the or
        << corresponds to the right shift in the figure above. In fact, << is the left shift.
        arr[index] |= 1 << position;
    }

    public void delete(int n){
        int index = n >> 3;
        int position = n & 0x07;
        arr[index] &= ~(1 << position);
    }

    public boolean contain(int n){
        int index = n >> 3;
        int position = n & 0x07;
        return (arr[index] & (1<< position)) ! =0; }}Copy the code

The problem

Have you seen the above code, have you found some problems?

For example, if we only store 1 number in bitmap and store 2000000000, we will change 0 to 1 in the 2000000000 binary. That is, the arR array size is at least 2000000000/8+1. However, there is no data stored in the front of the binary, which is not a super super waste of resources?

In fact, there are a lot of optimizations in Java bitmaps that don’t waste space as much as the code we implemented above. If you’re interested, you can look into it.

As for how to optimize it, I will talk about it in a future article.

For more original articles, you can follow my official account: the helpless and painful code farmer. I will share some resources and software from time to time. Send you a gift pack of current popular resources, and thank you for introducing the article to more people who need it