Analysis of internal storage mode of map in Java

Map, that is, map, also known as key value pair, has a key and a value.

For example, in groovy language, def map = ['name ':'liudehua','age ': 50], then the value of map ['name'] is' liudehua '. So how is map internal storage implemented? Let's explain it slowly

1、 Use zipper storage

This is explained by taking the HashMap in Java as an example. There is an array entry [] table inside the HashMap, which is used to store data.

The definition of the entry class is roughly as follows:

Therefore, each element of the entry [] table is a linked list, that is, the internal storage of HashMap is array + linked list, that is, zipper storage.

When putting (key, value) data into haspmap, first perform key Hashcode () & (table. Length () - 1), get a value less than table The value of length () is called index, and the new entry belongs to the linked list of table [index] (if the linked list does not exist, the new entry is used as the head of the linked list); Then start traversing the linked list of table [index] from front to back, if key Equals (entry. Key), which means that the key already has an old value, you can replace the value;

Otherwise, insert the new entry into the front of the table [index] linked list

The above is the storage method of HashMap. You can know that as the key of HashMap, its hashcode () and equals () methods are used

2、 Array storage

1. Decentralized array storage

This is based on ThreadLocal and ThreadLocal Values class as an example. There are two variables in the values class, object [] table and mask. Table is the array that stores data. The length of table is a multiple of 2, and the value of mask is table length - 1 ; This is very similar to the internal storage of HashMap. However, each element in the table is not a linked list.

When putting (key, value) into values, first enter key Hashcode & mask to get a value less than table The value of length is called index (like the HashMap above, ha ha). Then check the value of table [index]. If it does not exist, put key in table [index] and value in table [index + 1]; If it already exists, and the key If equals (oldkey) does not hold, that is, there is a conflict, then index = index + 2 (here is + 2, because key and value are placed next to each other, and one element accounts for two pits); Find the next place. If there is another conflict, find it again until you find a place to insert. Put table [index] = key and table [index + 1] = value;

There are two points to note:

key. Hashcode () must be a multiple of 2, otherwise the value of index may be odd, so a conflict may occur Refer to ThreadLocal Hash this member variable

The data inside the table is stored dispersedly

2. Continuous array storage

Take the new arraymap in android as an example (it is said that no arraymap is used to replace HashMap). There are two main variables in arraymap, int [] mhashes and object [] marays

Mhashes is mainly used to store the hash value of key. Mararies is used to store data. It also stores odd keys and even values. Keys and values are arranged in order (this is very similar to the table storage method in theadlocal.value). The length of M arrays is twice that of M hashes. After all, m arrays is a key and value should be saved~

The hash values of keys stored in mhashes are arranged from small to large. If the hash values of multiple keys are the same, they are arranged next to each other

When putting (key, value) into arraymap, int hash = key first Hashcode, and then find the position of the hash in mhashes through binary search (if there is one, return; if there is none, find the closest position first, and then reverse the operation and return) index. If index > 0, then go to 2 * index in marays to obtain the key value, and compare whether the two keys are equal (). If they are not equal, then go up Look down for the key with the same hash value nearby to see if there is a key of equals(). If so, replace it; if not, insert it; If index < 0, it means that no key of equal hash has been inserted before, then index = ~ index (take the opposite again, it is a positive number, and the agent will insert the position), then insert hash at the index of mhashes, insert key at 2 * index of marays, and insert value at (2 * index) + 1

be careful:

When inserting new data, both mhashes and marays need to move the data behind the insertion position backward by one unit, which consumes a lot for frequent insertion and deletion

The hash size of the key determines the insertion order

3. Array storage with number as key

This kind of map is special. Key is a numeric type. This is analyzed with the new SparseArray in Android. SparseArray has two main variables, int [] mkeys and object [] mvalues. Mkeys is an ordered array for storing keys, arranged from small to large; Mvalues is a set of value values corresponding to mkeys one by one The lengths of mkeys and mvalues are equal.

When putting (key, value) into SparseArray, first use binary search to find the location of the key in mkeys (if found, return; if not found, find the location where it should be inserted, reverse and return), and record it as index. If index > 0, directly replace value at mvalues [index]; If index < 0, then index = ~ index, i.e. negative, then insert key at the index of mkeys and value at mvalues [index], and move the previous data one unit back from the index.

be careful:

Both mkeys and marays need to move data during data insertion, which consumes a lot for maps that are frequently inserted and deleted Finally, we compare their advantages and disadvantages.

HashMap: large memory consumption, high efficiency of adding and deleting, and general efficiency of modifying and querying

ThreadLocal. Values: average memory usage. When the amount of data is small, the efficiency of adding, deleting, modifying and querying is high; When the amount of data is large, the efficiency of adding, deleting, modifying and querying is general

Arraymap: the memory occupation is small, the efficiency of modification and query is high, and the efficiency of addition and deletion is low

SparseArray: small memory consumption, high efficiency of modification and query, low efficiency of addition and deletion, and the primary key is a number

summary

We don't judge which storage method is good. Everything should be analyzed according to the actual situation to find the most suitable storage, ha ha ~. I hope it will help you. Interested friends can refer to: Java Bean and map mutual conversion method code example talking about the mutual conversion of object and map struts 2 using ognl to traverse the map method, etc. Thank you for your support.