Direction of performance optimization
Performance optimization is not overnight, should be in a variety of daily small details in a little bit of optimization, a little bit makes a lot, the app will be more smooth. One of the most important aspects of fluency optimization is the optimization of data structures.
Common list containers in Android: ArrayList, linkedList, HashMap, sparseMap, arrayMap
ArrayList
An ArrayList is a sequential list of arrays stored. If you don’t know what to use, you can use an ArrayList.
new ArrayList
New ArrayList does not pass the size of the array. The List is an empty array. If passed, it will be an array of new Object[I] size
add
There are two ways to add, one is to add directly, the other is to specify index add
- Add directly, if just new, does not specify the size (the array is empty). Let’s expand it to the default size (10).
1.2Direct add, array after the position (data 3 but elementData[] is 10), direct add. If the array is full when I add. Int newCapacity = oldCapacity + (oldCapacity >> 1); New = old + old>>1
- Add in the middle when add, first check the array out of bounds + expansion problem. then
arraycopy(ArrayCopy iterates and moves the index back one bit.)
remove
Remove, like add, is also a System. Arraycopy moves the following one bit forward
conclusion
ArrayList add and Remove frequently copy the entire list, which affects performance. That is to say, ArrayList is fast in search (because it is stored in an array, an array is a continuous piece of memory, it is easy to calculate the specific address of the data store by the array head + I * data size, so get is fast), add and remove are fast in the tail operation, and the middle operation is slow.
linkedList
To solve the problem of ArrayList add and delete operations being slow, there is linkedList. LinkedList is a two-way linkedList loop structure.
Each node has a precursor node, and a rear-drive node, pointing to the previous node and the next node.
add
- Tail add node
- Adding nodes in the middle
final Node
newNode = new Node<>(pred, e, succ); New = new = new = new = new
remove
If you add a new node, the node will become unreachable and will be reclaimed.
conclusion
Add and remove the linkedList without moving the list, so fast. However, when querying and modifying linkedList, unlike ArrayList, which is stored in an array, there is no quick way to find the storage address, so you have to go through it one by one, so it is slow.
HashMap
Both linkedList and ArrayList have their drawbacks, so if you want all the good at the same time, you have HashMap.
There are two versions of HashMap. Before java1.7 before android 24: arrays + lists after 1.8: arrays + lists + red-black trees
Array + list transient HashMapEntry
[] table = (HashMapEntry
[]) EMPTY_TABLE
: Table array stored HashMapEntry
such a linked list.
It looks something like this
HashMapEntry
[] Table vertical is the table array, the array stored such as HashMapEntry
key, value structure. Table The default length of the table array is
put
When put stores a value
A key can be any object, but any object has its HashCode, and an object’s HashCode approximates its storage address and is a unique int value. Tab.length = HashCode%length = hash & (tab.length – 1)
Table [].length=16, hashCode%length=344413%16=13 Therefore, the map value exists in table[13]
This process of adding is called boxing
If you add a new value, hashCode%length will give you a value that already has data in it.
The new node is then placed at the head of the original list and inserted. This is called a head insert or head insert.
When you insert something that already has a linked list in place, it’s called a hash collision or hash collision
Additional knowledge:
- Source code for remainder algorithm hashCode % length, with is
int index = hash & (tab.length - 1);
Because for efficiency, the decimal +-*/%… Operations at the bottom of the CPU are converted to binary operations, so it is more efficient to use binary operations directly.
- How do you put keys and values one to one.
When put, it will first go to the place of the table based on the hashCode of the key, and then for traverses the list behind it. It will find out if the hashCode has a value, and if so, change the value directly. It’s not being added
Resolving hash collisions
For example, the hashmap is constantly adding nodes to it. As the table[] becomes more and more full, the hash collisions become more and more likely. To solve this problem, the table needs to be expanded.
So when to expand? What is full?
After complex calculation and testing, mathematicians calculate that when the space is 60%~75%, the hash collision is very serious and needs to be expanded. Therefore, we set 0.75 as the best state before expansion, which becomes the loading factor.
Threshold Threshold = Loading factor * table.length. That is, threshold = 0.75 * 16 = 12. When length is 16, 12 data are added to it. If you add more data to it, you have to expand it.
Expansion Expansion is to reduce hash collisions. How to expand: Since the length value changes, the hashCode % length changes, so each expansion will add each data piece to the new empty HashMap one by one. So scaling up is very performance intensive, which requires that we try to estimate the size of the HashMap when we create a new HashMap, and then create a HashMap of that size. New HashMap (0.75 * size + 1)
new HashMap
When creating a new HashMap, try to estimate the size of the HashMap and create a HashMap of that size. New HashMap (0.75 * size + 1)
- Direct new HashMap
To waste memory, if you simply new a HashMap, the HashMap will be empty, and you will only create the table[] the first time you put the data. This is what other lists do. (Default size is 16)
- New HashMap (int) is created with the size specified
If you specify a size, like new HashMap (10), you’re not going to create a HashMap of 10, you’re going to create a HashMap of the nearest 10 to the NTH power of 2, so you’re going to create a HashMap of 16 that’s going to have a size of 2 to the NTH power, and you’re going to do this for efficiency, and you’re going to do this efficiently in binary
The size of the HashMap is 2 to the NTH power, and this is done because it’s efficient, and it’s efficient when you do binary arithmetic hash & (tab.length – 1)
Example: 6&10 and 6&16 110 & 1001 and 110 & 1111 (& – two 1’s are 1, otherwise it is 0) (XXXX & 1001) The significant digits are two 1’s, so the middle two digits of XXXX are 00 no matter what, only the first and last two digits are optional. That is, there are only 1000,1001,0000,0001 cases (8,9,0,1). The fewer cases, the higher the probability of hash collisions.
get
When get is used, first fetch the index list after TAB [] according to TAB [hash & (tab.length-1)]. And then go through the for loop according to the hashCode.
HashMapEntry
HashMapEntry this HashMapEntry doesn’t just have keys and values in it. It actually has the hashCode value and the next next node
resize
If table == NULL, this is the initialization of HashMap, and an empty table is returned. NewLength = oldLength << 1 if the table is not null; newLength = oldLength << 1 if the table is not null; newLength = oldLength << 1; 3 iterate oldTable: 3.2 If the first node is empty, the loop ends; 3.1 If there is no subsequent node, recalculate the hash bit and the loop ends; 3.2 The current is red black tree, red black tree relocation; If the current list is a linked list, the hash bit needs to be recalcuated in JAVA7, but JAVA8 is optimized by (e.ash & oldCap) == 0 to determine whether shift is needed; If it is true, it stays in place; otherwise, it needs to move to the current hash slot + oldCap;
For example, 16 is expanded to 32
Because it doubles exactly, which means binary has an extra 1 on the left. Everything else is the same, just focus on the first place. So when the first digit is zero, we don’t move. If the first digit is 1, move oldCap to oldCap + I
This is why the length of a HashMap must be a multiple of 2.
Because of this interlocking design, it makes sense that hashMap.loadFactor has a value of 3/4, Table.length * 3/4 can be optimized as (table.length >> 2) << 2) – (table.length >> 2) == table.length – (table.lenght >> 2), JAVA bit operations are more efficient than multiplication and division, so the selection of 3/4 is considered efficient with little hash collisions.
conclusion
Unlike ArrayList and linkedList, hashMap is fast and can be added, deleted, and checked quickly. But hashMap scaling is very inefficient, and scaling is a multiple of two. For example, if the size of a new hashMap is 64, expanding it to 128 is wasteful and slow, so you need to create a new hashMap with an estimated amount of data.
And hashMap has a load factor of 0.75, which means that the highest space utilization is 75%, which means that hashMap trades memory space for speed
SparseArray
To address the shortcomings of HashMap, Android has created its own SparseArray. SparseArray = HashMap + binary search idea
The structure of the SparseArray
The two arrays correspond to each other, storing key and Value respectively
put
Keys can only be ints, and arrays of keys are ordered.
Put overall code
Binary search
Back operation
remove
When you remove, you don’t delete the intermediate nodes and then move them forward by one. If the node is DELETED, it is marked as “DELETED” without moving the next node. So the next time you add it, you just add it, you don’t have to move it all back. In this way, the key between 30 and 500 can be added directly next time, so the efficiency of SparseArray is faster and faster.
new SparseArray
Default size 10, or specify
conclusion
SparseArray performs slightly better overall than HashMap. SparseArray also features faster use. Disadvantages: Key can only be an int
arrayMap
arrayMap = HashMap + SparseArray
The lookup in a structured ArrayMap is a two-step process
Find the index value in the mHashes array according to the hashcode of the key and find the corresponding value of the key according to the index value of the previous step
The most time complex part belongs to the first step: determining the index value of the key’s hashCode in mHahses. In this step, Binary Search is used for mHashes Search. So the query time for ArrayMap is astrologer O log n.
The interview questions
- What is the underlying principle of HashMap? Is it thread safe?
Hash table is composed of an array + a linked list… See above: HashTable is thread safe,HashMap is thread unsafe. In the case of multiple threads, the HashMap will loop indefinitely.
- The difference between HashMap and HashTable
- A hashmap concurrenthashmap principle
ConcurrentHashMap provides simple, secure, and inexpensive HashMap synchronization.
The synchronized lock is applied to the entire Hash table, i.e. each operation locks the entire table; ConcurrentHashMap allows multiple modification operations to be performed concurrently using Lock Stripping, or segmenting locking, or Stripping technologies. Segment locking uses multiple locks to control changes to different parts of the hash table. ConcurrentHashMap internally uses segments to represent these different parts, each of which is essentially a small hash table with its own lock. As long as multiple modification operations occur on different segments, they can be performed concurrently. Because of the concurrency concept, the efficiency is significantly improved over full locking.
- What’s the difference between ArrayList and HashMap?
- How is the capacity expansion resize() implemented….