[HBZ share] reasons for slow addition and deletion of ArrayList and fast query

ArrayList When is the query fast ?

1. Only by subscript index When inquiring , Very fast performance , Because you can directly find the corresponding data in the following table , Time complexity O(1)
2. When non subscript query , But through for Loop to traverse , The performance is not fast , Time complexity O(n)
3. myth ： Many people mistakenly think ArrayList Any inquiry is fast , It's actually wrong , Only through index Our inquiry is very fast

ArrayList Why the increase of performance is slow

1. In image ArrayList Add elements to add When , Could lead to List Expansion of , because ArrayList The bottom layer is array structure , But the data does not support dynamic expansion , therefore ArrayList The capacity expansion mechanism of is to create a new array , Migrate the array data to the new array , Then add new elements
2. The expansion mechanism is , If the original array does not exist , And expand the capacity directly 10 individual . If the original array exists , Then expand 1.5 By , namely oldSize + oldSize >> 1

ArrayList Why is the deletion performance slow

1. Deletes the specified element ,ArrayList The bottom layer is actually deleted from index The position is the starting point , All elements to the last , Move one bit forward , Then set the last bit to null
2. Move all elements , In fact, it is through the bottom System.arraycopy(), The array of index+1 Position start , Copied to the index Location , Then the last one =null
3. So the process will be slow

ArrayList Modification of

1. Modification is the same as query , When specifying index when , Directly modifying , A high performance O(1)
2. When the cycle for To modify , Then the performance is low O(n)