Java notes: Collections

A collection is a kind of container object, which is used to store objects, or stored references to objects. It is not a directly stored object, but the memory address of the stored object. It should be noted that the basic data type cannot be stored in the set. Even if the basic data type is added to the set in the code, it is put into the set after automatic boxing.

It should be noted that for each different collection in Java, the underlying layer will correspond to different data structures, so the appropriate collection type should be selected and used according to the actual situation.

All collections are in "Java. Util". You can find them in the util package when importing.

Note: the syntax represented by angle brackets such as < E > is often seen in the definition of collection. This is the definition of generic type, which means that the type you need can be passed in as needed. If it is not passed in, it is the object type by default. That is, if the specified type is passed in, only the specified type can be stored in the collection. Otherwise, all subtypes of the object class can be stored in the collection.

1. Collection inheritance structure

A collection of type collection is characterized by storing elements as individuals of a single object.

java. lang.Object --> java. util. Abstractcollection < E > this class implements the following two interfaces:

Common methods in the collection < E > interface:

Methods commonly used in iterator < E > iterator():

Common sub interfaces under collection < E > interface:

Common methods in the list < E > interface:

2. Map collection inheritance structure

The collection feature of map type is to store collection elements in the form of key and value pairs, that is, a key value pair is counted as a collection element.

java. util. Common methods in map < K, V > interface:

java. util. Common implementation classes of map < K, V > interface:

3、ArrayList

Features: set elements are orderly and repeatable. Set elements can be accessed through subscripts, and are non thread safe.

Methods: the ArrayList < E > method in the collection < E > and list < E > interfaces can be used.

Thread safe: if you want to make ArrayList < E > thread safe, you can pass in your ArrayList object through the synchronizedlist (yourlist) method of "Java. Util. Collections", and then the ArrayList will become thread safe.

Underlying principle: the underlying of ArrayList adopts the data structure of object type array. When creating an object, you can pass in the size of the array. If no array size is passed in, an empty list will be created during initialization, and then an array of size 10 will be created when adding data to it for the first time. When adding data to the array, if the capacity is full, the array will be automatically expanded, and the capacity of the expanded array will be 1.5 times of the original capacity.

Advantages and disadvantages: just like the advantages and disadvantages of arrays, query efficiency is very fast, and adding data to the end is also very fast. However, the efficiency of random addition and deletion of elements is low, so the use of random addition and deletion and capacity expansion should be avoided as far as possible.

Use example:

4、LinkedList

Features: set elements are orderly and repeatable, and set elements can be accessed through subscripts.

Methods: the ArrayList < E > method in the collection < E > and list < E > interfaces can be used.

Underlying principle: the underlying layer adopts the data structure of a two-way linked list. During storage, the elements will be encapsulated into a node object. In addition to the element itself, this node object also has two variables next and prev for the addresses of the next node and the previous node, so as to form a "two-way" linked list. Although it is a linked list, you can still use subscripts, but it is not recommended to use subscripts for query, because each query has to start from the node, which is inefficient.

Advantages and disadvantages: the query efficiency is low, because the query starts from the node every time, but the efficiency of randomly adding and deleting elements is high, because it will only involve the modification of variables next and prev in the previous node and the next node, and will not involve the overall movement of the value after the element like the array. Therefore, in terms of selection and use, if there are many random additions and deletions, you should use LinkedList. If you need to frequently add or query data to the collection, you should use ArrayList.

Capacity: because LinkedList is a linked list data structure, there is no continuity in memory space, and there is no capacity. At first, it is empty without any elements.

5、Vector

Like ArrayList, vector has an array data structure at the bottom, which is also the same in use. The difference is that vector is thread safe, but it also leads to low efficiency. ArrayList can use other better methods to ensure thread safety, so vector has been used less.

6、HashSet

Features: set elements are out of order and cannot be repeated. Set elements cannot be accessed through subscripts.

Methods: the methods ArrayList < E > in the collection < E > interface can be used.

Underlying principle: the underlying layer of HashSet actually uses HashMap type to store elements, but only the key part of HashMap is used, and the value part is not used. The key of HashMap itself is disordered and non repeatable, so it can be regarded as that all the keys of HashMap form a HashSet. So for a better understanding of HashSet, see the notes in the HashMap section.

7、TreeSet

Features: set elements are out of order and cannot be repeated. Set elements cannot be accessed through subscripts, but the data stored in the set is automatically arranged in ascending order.

Methods: the methods ArrayList < E > in the collection < E > interface can be used.

Underlying principle: because TreeSet implements sortedset, the stored elements are arranged in good order. The disorder in "disorder cannot be repeated" refers to the inconsistency between the order of storage and extraction, which is different from the automatic sorting after storage. Don't get confused. Similar to HashSet, the underlying TreeSet actually uses the treemap under the map to store data. It also uses only the key part of the treemap instead of the value part. Therefore, to understand TreeSet, please refer to the notes in the treemap part.

Automatic sorting: in order to change automatic ascending to automatic descending, or when storing custom types, you need to override or customize the sorting mechanism of TreeSet, especially the custom types. If the sorting mechanism is not defined at the same time, an error will be reported, The custom sorting mechanism is to implement the "Java. Lang. comparable" interface for this custom class or customize a comparator "Java. Util. Comparator". Examples are as follows:

8、HashMap

Features: key value pairs are used to store data. Key is out of order and cannot be repeated. Value can be repeated and is non thread safe.

Underlying principle: the underlying layer of HashMap is actually a hash table or hash table data structure, and this hash table is composed of an array, a one-way linked list or a red black tree. During initialization, it is a one-way linked list. When the added element causes the number of nodes in the one-way linked list to exceed 8, it will be automatically converted to a red black tree. If the number of nodes in the red black tree is less than 6, It will be automatically converted into a one-way linked list. The reason for this implementation is to query the collection elements more quickly. The array part is actually a one bit array of node type. Each element is a node object. The node object has four basic attributes: "final int hash", "final K key", "V value" and "node < K, V > next". Hash represents the hash value returned by the hashcode method rewritten from the object, And this hash value can pass another hash algorithm at the bottom (this algorithm needs no attention) get the corresponding array subscript, that is, the hash value can be regarded as corresponding to the array subscript, or it can be directly regarded as the array subscript, and next represents the memory address of the next node. Take the initial array and one-way linked list as examples, and use the put method and get method to explain the principle of HashMap in more detail.

Principle of put method: when the put method is executed to store a key value pair into the HashMap set, the following steps will be followed:

Principle of get method: when a key value is used to obtain the corresponding value through the get method, the following steps will be followed:

Rewriting of hashcode () and equals () methods: it can be seen from the implementation principles of put and get above that the hash values of all nodes on the one-way linked list at the same array position are the same, but the return values of equals method of key must be different. It can also be found that when using HashMap, the key object needs to override two methods, hashcode () and equals (). When overriding the hashcode method, you should pay attention to the following:

Array capacity: the default capacity of the HashMap set is 16, and the default loading factor is 0.75, which means that the default array length is 16. When the actual array usage reaches 75% of the capacity, it will be automatically expanded, and the capacity after expansion is twice the original capacity. You can also specify the capacity size during initialization, but the official recommendation is that the initialization capacity should be a multiple of 2, otherwise it will affect the execution efficiency of HashMap.

Use example:

9. Hashtable < K, V > and properties

The use of hashtable and HashMap is similar. The difference is that hashtable is thread safe and the latter is non thread safe. However, as in the case of vector, the implementation of hashtable thread safety leads to low efficiency, so it is used less.

A subclass of hashtable, properties, is more commonly used. Properties are also thread safe. Properties objects are also called property objects. Its feature is that both key and value only support string types. Common methods are:

Note: at the end of the "Java notes: IO flow" note of "10. IO and properties are used together to read configuration files", there is a use example of properties, which can be referred to below.

10、TreeMap

Features: key value pairs are used to store data. The key is unordered and cannot be repeated. The value can be repeated, and will be automatically sorted according to the ascending order of the key after storage.

Underlying principle: treemap implements the SortedMap < K, V > interface, and the underlying is actually a data structure of self balancing binary tree. This data structure stores data according to the principle of small on the left and large on the right. The stored key and value are actually encapsulated in an entry < K, V > node object. In addition to the stored key and value, this node object also has three variables left, right and parent to store the memory addresses of the left child node, the right child node and the parent node, which just forms a binary tree. When traversing the binary tree, there are usually three ways: pre order traversal (left and right roots), middle order traversal (left and right roots) and post order traversal (left and right roots). This "front, middle and back" refers to the position of the root (node) relative to the "left and right" or the order in traversal. For middle order traversal, the feature is that the traversed data is automatically sorted from small to large.

11. Collections tool class

This class specifically defines some methods that facilitate collection operations. Common are: