We talked about BitMap How to store data , You can have a look if you haven't seen it 【 Algorithms and data structures 】BitMap Algorithm is introduced

Let's talk about BitMap The code implementation of this data structure .

Review the principle of data storage

A binary bit corresponds to a nonnegative number n, If n There is , Then the value of the corresponding binary bit is 1, Otherwise 0.
This is the time , Our first question ：
We are using byte,int,short,long When these data types store data , The smallest of them takes up a byte of memory , That is to say 8 individual bit, in other words , The smallest unit of operation is 8 individual bit. There's no way to... One by one bit The data type of bit operation .

stay Java Of bitMaP In the implementation , It uses a long Data for storage . One long Occupy 8 Bytes , namely 64bit, So a long Can be stored 64 Number . for example arr It's a long An array of types , be arr[0] Can be saved 0 ~ 63,arr[1] Can be saved 64 ~127, And so on .
however , We will adopt byte Array to save it . One byte Take up one byte , namely 8bit, Can be saved 8 A digital .
Of course , You have to use long Array can also be saved . It's the same in terms of implementation .
For example, we want to store (1,3,5,7,8,10) when , Their memory is as follows .

Now let's talk about how to operate bit by bit .

How to talk to bitmap Add a value to

Let's talk about how to bitmap How to add a numerical value in , For example, we're going to add n=14.
This is very simple , Let's find n stay arr Subscript in array index, obviously index = 1. And then find n stay arr[index] Position in position, Clearly here position = 6.
It's still easy to find out index and position The formula of . namely
index = n / 8 = n >> 3.
position = n % 8 = n & 0x07.

Next, we will 1 To the right position Binary bits , Then compare the results with arr[index] do “ or (or)” Operation is OK . Here's the picture

There's something to pay attention to here , When drawing , For convenience , We take the left bit as Low position , The bit on the right is High position Come on . But in real storage , The one on the left is the one on the left , And the one on the right is low . So in our code implementation , What we call right shift corresponds to left shift of code .
Code implementation

// Add data operations 

public void add(int n){

// use >> The operation of , It's going to be faster 

int index = n >> 3;

int position = n & 0x07;

// hold 1 Move right and do or Two steps together 

// namely << Corresponding to the right shift in the figure above , actually << It's left shift .

arr[index] |= 1 << position;

}

got it add operation , Other operations are similar .
Of course , What we achieve add The operation is just a simple implementation , If you're going to do it rigorously , It still needs a lot of abnormal judgment . For example, judge whether the number is non negative , Judge arr Whether the subscript of the array is out of bounds , Capacity expansion and so on . If you are interested, you can implement it .

Delete operation .

We just need to put the corresponding binary 1 become 0 That's all right. .
We can 1 Move right ( Shift left in the code ) The result is reversed , Then with arr[index] do “ And ” Operation is OK . The code is as follows ：

public void delete(int n){

int index = n >> 3;

int position = n & 0x07;

arr[index] &= ~(1 << position);

}

Determine if there is an operation

We put 1 After right shift , Compare the results with arr[index] do “ And ” operation , How the result is not 0, Then prove the existence of , Otherwise it doesn't exist .

public boolean contain(int n){

int index = n >> 3;

int position = n & 0x07;

return (arr[index] & (1 << position)) != 0;

}

The three most basic operation codes are basically implemented .
I hope you can practice it .
All the code ：

public class BitMap {

private byte[] arr;

// Capacity , That is, how many data can be stored at most 

private int capacity;

public BitMap(int capacity) {

this.capacity = capacity;

// One byte Can be saved 8 Data ,capacity Actually, it means how many bit

arr = new byte[(capacity / 8 + 1)];

}

// Add data operations 

public void add(int n){

// use >> The operation of , It's going to be faster 

int index = n >> 3;

int position = n & 0x07;

// hold 1 Move right and do or Two steps together 

// namely << Corresponding to the right shift in the figure above , actually << It's 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;

}

}

problem

You see the above code , Have you found any problems ？

For example, we are only bitmap Storage 1 Number , And the stored value is 2000000000, We'll be in the second 2000000000 It's a binary 0 Change it to 1. in other words arr The size of the array is at least 2000000000/8+1. But at this time, the front binary does not store data , It's not a super waste of resources ？

So , Like the way we write it above, it can be said that violence How to write it , Without any optimization , actually , stay Java Self contained bitMap There are a lot of optimizations in , It doesn't waste as much space as the code we implemented above . Those who are interested can study .
How to optimize , I'll talk about it later , Look forward to it .

For more original article , I can pay attention to my official account ： Hard pressed Manon , I will share some resources and software from time to time . The background to reply Gift bag Send you a current popular resource gift package, but also thank you for introducing the article to more people in need