## Time complexity analysis of Java collection class

The blog of clayhub 2020-11-06 01:18:20
time complexity analysis java collection

### introduction

The concept of progressive time complexity ：
If there is a function f（n）, Properly n Approaching infinity ,T（n）/ f（n） The limit value of is a constant not equal to zero , said f（n） yes T（n） Functions of the same order of magnitude of . Write it down as T（n）= O（f（n））, call O（f（n）） Is the incremental time complexity of the algorithm , Time complexity . Progressive time complexity in uppercase O To express , So it's also called big O notation .

Time complexity derivation principle ：

• If the run time is constant , With constant 1 Express .
• Only the highest order term in the time function .
• If the highest order term exists , Then the coefficient before the highest order term is omitted .

### 1、 List

#### 1.1、ArrayList

• add(E e) Method inserts... Directly at the end of the array , The time complexity is O(1)
• add(int index, E element) Method to specify index insertion , There will be data movement , The time complexity is O(n)
• get(int index) According to the index of the array , Time complexity O(1)
• remove(int index) After deleting , There will be movement of data , Time complexity O(n)

• add(E e) The tail interpolation , The time complexity is O(1)
• add(int index, E element) Insert... At the specified location , Need to loop to get the insertion position , Time complexity O(n)
• get(int index) Get the specified location node , Order traversal list , The time complexity is O(n)
• remove() Delete header node , Time complexity O(1)

### 2、Set

#### 2.1、HashSet

• add(E e) The bottom is HashMap Of put(K key, V value) Method ,JDK1.8 Red black tree introduced , When hash The length of the list of nodes in the table reaches the treeling threshold 8 when , It will turn into a red black tree , The insertion time complexity is O(logn).

As long as the red and black trees are introduced , Insert 、 Delete 、 When looking for , The time complexity becomes O(logn).

#### 2.2、TreeSet

The bottom layer is TreeMap, Use red black tree to achieve , The time complexity of insert delete search is O(logn).