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

【 Algorithms and data structures 】BitMap Algorithm basic operation code to achieve more related articles

  1. python Algorithm and data structure - Choose a sort algorithm (33)

    One . Introduction to selection sorting Selection sort (Selection sort) It is a simple and intuitive sorting algorithm . First, find the minimum in the unsorted sequence ( Big ) Elements , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements ( Big ) Elements , ...

  2. python Algorithm and data structure - Hill sort algorithm (35)

    One . The introduction of Hill sort Shell Sort (Shell Sort) It's a sort of insertion sort . Also known as reducing incremental sorting , Is a more efficient and improved version of the direct insertion sort algorithm . Hill sort is an unstable sort algorithm . Hill sort is to group records by a certain increment of subscript , For each ...

  3. Big data sorting algorithm : External sorting ,bitmap Algorithm ; Big data De duplication algorithm :hash Algorithm ,bitmap Algorithm

    External sorting algorithm : Mainly used in merge sort , Heap sort , Bucket sort , The point is to break it into different pieces first , Then find the minimum value from each block and write it to disk , The analysis process can be seen http://blog.csdn.net/jeason29/article/ ...

  4. python Algorithm and data structure - Algorithm is introduced (31)

    One . Algorithms and data structures What are algorithms and data structures ? If we compare the final written program to the battlefield , Our programmers are the generals who command the war , And the code we wrote was soldiers and weapons . So what are the data structures and algorithms ? answer : The art of war ! so , Data structure and algorithm are a kind of ...

  5. Massive data processing -BitMap Algorithm

    One . summary This article will cover Bit-Map The related principles of the algorithm ,Bit-Map Some application scenarios of the algorithm , for example BitMap Solve massive data to find duplication . Judge whether individual elements are in the mass data . Finally, BitMap The features have been in various scenes ...

  6. Algorithm ——001BitMap( Bitmap ) Algorithm

    Hash table has the advantage of O(1) Constant time of , Often used for performance optimization , But memory is limited after all , When the amount of data is too large, the hash table will overflow the memory . And there are some problems when we consider storing and batch processing these big data IO Overhead on , The performance can not meet the requirements . This ...

  7. Programmer code interview guide IT Famous enterprise algorithm and optimal solution of data structure problem

    Link to the original text This is a programmer interview guide ! The book is right IT The best solution of all kinds of questions in the code interview of famous enterprises is summarized , And provides the related code implementation . In view of the current programmer interview lacks authority topic summary this pain point , This book selects nearly 200 A real classic code interview question , help ...

  8. data structure (DataStructure) And algorithms (Algorithm)、STL application

    catalogue . Introduction . The concept of data structure . Examples of logical structures 2.1 Stack 2.2 queue 2.3 A tree structure Binary tree . Examples of physical structures 3.1 Linked list One way linear list One way circular list Bidirectional linear list two-way ...

  9. Daily exercise of classic algorithm problems —— Eleventh questions Bitmap Algorithm

    original text : Daily exercise of classic algorithm problems -- Eleventh questions Bitmap Algorithm In all data structures with performance optimization , I think what you use most is hash surface , Yes , Have... On have location lookup O(1) Constant time of , How simple and beautiful , But in a particular field ...

Random recommendation

  1. About closure (closure) Some of the concepts of

    Like most other modern programming languages ,JS Also use lexical scope , in other words , The execution of the function depends on the scope of the variable , This scope is determined when the function is defined , It's not a function call . To achieve this lexical scope ,JS The internal state of a function object contains not only ...

  2. Java Programmers from stupid to rookie ( One hundred and one )sql Injection attack details ( Two )sql The injection process is explained in detail

    In the last blog, we analyzed sql Injection principle , Let's take a look at sql The whole process of Injection , In other words, how to carry out sql Inject , Due to my limited knowledge of database and network , This article is an analysis and summary of a large number of similar articles on the Internet , Many of them are directly quoted ...

  3. django Of models Module query method

    Assume models There is a class in BookInfo Module query is different from sql sentence , The result of the module query will return the whole line of objects that meet the conditions , Or a query set of multiple objects . A query set is like a list , There's a similar approach . 1 model Query statement : ...

  4. Never call out of the loop wait Method

    1. Preface With the failure of Moore's law ,Amdahl The law has become a guide to the development of multi-core computer performance . For the present java For programmers , Concurrent programming is becoming more and more important and common . I'm ashamed and scared of java Concurrent programming has always been conceptual , Enter into ...

  5. cmake A concise guide to use

    cmake A concise guide to use Last update 2018/8/8 Execute first cmake Generate makefile, Then take a look at the contents ,( At least in the ubuntu16.04 Upper cmake3.5.1 On ), The following is provided : ...

  6. idea Easy to set code snippet

    Using shortcut keys (ctrl+alt+s) find : from idea Menu for File->Settings->Editor->Live Templates To add Template Group, Then add Li ...

  7. Android Medium and long distance Service elementary analysis

    In the last article, I simply wrote about Android in Service There are two ways to start , But it's all local services , Today, simply write down about Android Medium and long distance Service Use , Learn about two concepts before you learn ,AIDL( And ...

  8. Swift - WebKit Example interpretation

    If you've ever been in your App Use in UIWebView Load the web content , You should be aware of its many unsatisfactory aspects .UIWebView It's based on the mobile version Safari Of , So its performance is very limited . Especially for almost every Web Should be ...

  9. hdu4085 Peach Blossom Spring

    Peach Blossom Spring http://acm.hdu.edu.cn/showproblem.php?pid=4085 Time Limit: 10000/5000 MS (Java/ ...

  10. matlab solve equations

    [x1,y1,x2,y2]=solve('x1^2 + y1^2=1','x2^2-8*x2 +y2^2 +15=0','x1*x2 + y1 * y2=1','x1 + x2 =a','x1','y ...