Underlying implementation of ArrayList, LinkedList and HashMap

The bottom implementation of ArrayList is an array (fixed size). When the length of the array is not enough, a new array will be opened up, and then the original data will be copied to the new array.

The underlying layer of LinkedList is a linked list, which is a two-way linked list implemented by Java. Its nodes are as follows:

class Node

{

　　private Node privIoUs;// Point to previous node

　　private Object value;// Value of the current node

　　private Node next;// The value pointing to the next node, similar to a pointer.

}

Then the operation of adding, deleting, modifying and querying is realized, which is exactly the same as that of the linked list in the data structure, and the insertion is orderly.

The bottom layer of HashMap is an array + linked list implementation. The basic principle is: define an array of LinkedList, and then store the data in the linked list array, for example: LinkedList [] list = new LinkedList [1000]; This defines a data structure as shown in the following figure:

The upper row is an array, and an element in the array corresponds to a linked list. When inserting elements, first calculate the hash value H according to the key value, then calculate H% 1000 to get a number, and then insert the object into the corresponding array element: for example, if h% 1000 gets 10, insert the object into the list [10]. Inserted

The content is a data item, and its structure is as follows:

class{

　　String key;

　　Object value;

}

The underlying implementation of HashSet is implemented through map. Duplicate elements are not allowed in the set, which is similar to the set. During the implementation of HashSet, it is implemented through map. Each time data is added to the set, the data will be set as the key value of map, and the value of map will be set as a default value. Because the key value of map cannot be repeated, it will be added to the set every time

The data cannot be repeated.

The above is just my simple understanding. You can watch the source code for learning and analysis.