Analyze the internal mechanism principles of common collections in JAVA

Everyone is familiar with commonly used collections, but they may only have a little understanding of the internal principles. The following is understood by reading the source code.

ArrayList

ArrayList internally is a dynamic object array container with a default size of 10. Whenever a new data is added, if it is larger than the original container size, the container size will be increased through Arrays.copyOf to 1.5 times the original, and so on. When the data size can be predicted, the size of dynamic data can be set by default to reduce resource consumption caused by expansion.

Time complexity:

get() - Read the subscript directly - O(1)

add(E) - Add directly after - O(1)

add(idnex, E) - After inserting data, you need to move the following data - O(n)

remove(index) - After deleting, you need to move - O(n)

LinkedList

LinkedList is a doubly linked list. When adding new data, you actually call linklast to insert data at the end of the linked list. When deleting, you can directly find the corresponding data and replace the previous and next nodes of the linked list.

Time complexity:

get() - needs to be traversed - O(n)

add(E) - call linklast to add directly at the end - O(1)

add(index, E) - You need to find the data at the original index position first, and then re-specify the data before and after the linked list - O(n)

remove() - Directly call removeLast to delete the last data - O(1 )

remove(index) - You need to find the data at the original index position first - O(n)

HashMap

HashMap is actually an array inside, and each array is a one-way linked list. The array in HashMap is a class named Entry, which contains (key, value, next). These attributes. The storage rules are: the array subscript is obtained by hash(key)%len. After obtaining the array, the HashMap also has a load factor (default 0.75), when the array is 75% filled. When put, it will be expanded to 2 times the original size.

Then the question is, if the values ​​of hash(key)%len are equal during put, won’t there be a conflict? The processing method of HashMap is: there is originally an Entry[0] = A, and then a B with an index of 0 comes, then Entry[0] = B, B.next = A, and when another C comes, then Will Entry[0] = C, C.next = B, and so on. In this way, Entry will form a linked list, and when fetching, the linked list will be traversed to obtain the value.

What needs to be mentioned here is that when using hashMap, the introduced key object must rewrite the two functions of hashCode() and equal(). The reason can be referred to the source code judgment condition (if (e.hash == hash && ((k = e.key) == key || key.equals(k)))), if hashCode() is not rewritten, the corresponding array cannot be found at all. If equal( ) is not rewritten, it is impossible to determine whether the contents of the key values ​​are equal.

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null总是放在数组的第一个链表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍历链表  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            //如果key在链表中已存在，则替换为新value  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
}

Supplement:

Hashmap has been optimized after java8: Since the querytime complexity of a one-way linked list is O(n), in extreme cases There may be performance issues, so if the linked list length is greater than 8, Java8 will use a red-black tree with a time complexity of O(log n) for storage to improve the efficiency of storage queries.

LinkedHashMap

The combination of the internal doubly linked list of LinkedHashMap and HashMap supports multiple iteration orders. The default is insertion order, and it can also be in access order.

Access order (accessOrder=true): The elements accessed by calling get will be placed at the end of the chain, and the iteration will start from the beginning of the chain.

Insertion order (accessOrder=false): Iterate in the insertion order Come out

TreeMap

TreeMap is internally implemented based on red-black trees, and will be naturally sorted by key type through compareTo by default. The lower level of TreeSet is TreeMap.

The above is the detailed content of Analyze the internal mechanism principles of common collections in JAVA. For more information, please follow other related articles on the PHP Chinese website!