Detailed explanation of Java collection inheritance system

Java's collection class is a particularly useful tool. It can be used to store multiple objects with different numbers, and can implement common data structures, such as stack, queue and so on. Java collections can also be used for associative arrays with mapping relationships.

A Java collection is like a container. We can save multiple objects (actually object references, which are customarily called objects) into the collection container. Before JDK1.5, Java collection will lose the data types of all objects in the container. After JDK1.5, generics are added. Java collection can remember the data types of objects in the container.

Java collections can be roughly divided into three systems: set list map All collection classes are located in Java Under util package.

Collection interface

The collection interface is the parent interface of the list, set, and queue interfaces. Collection represents a rule, and all elements contained in it must follow one or more rules. For example, some allow repetition, some cannot, some must be inserted in order, some are hash, some support sorting, and some do not support sorting.

1、 List interface

The list interface is the direct interface of the collection interface. List represents an ordered collection, and each element in the collection has its corresponding index. Duplicate elements are allowed in the list. You can access the collection elements at the specified location through the index. Because the list collection sets the index of elements by default in the order in which they are added.

（1）ArrayList、Vector、Stack

ArrayList and vector, as two typical implementation classes of list, fully support all functions of list.

The bottom layers of ArrayList and vector classes are based on arrays to store collection elements, encapsulating a dynamic object [] array, which is a sequential linear table.

ArrayList and vector are almost identical in usage, except that vector is in jdk1 It exists at 0. Its method name is relatively lengthy, contains more methods than ArrayList, and the source code contains more source code than ArrayList. The serialization implementation of ArrayList is better than vector. Now vector is basically replaced by ArrayList.

Main difference: ArrayList is thread unsafe and vector is thread safe.

If you need to use the list collection in a multi-threaded environment and ensure thread safety, you can still avoid using vector and consider packaging ArrayList as a thread safe collection class. The collections tool class provided by java can wrap ArrayList into thread safe ArrayList through the synchronizelist method of this tool class

Stack

Vector provides a subclass, which is used to simulate the data structure of "stack". Stack is usually a first in and last out container. Stack provides five additional methods so that vector can be used as a stack. Pop out of the stack, push into the stack, access the top element peek(), judge whether the stack is empty empty(), and detect the position of an element in the stack serch()

(2)LinkedList

LinkedList is a linear variable stored in a chain. In essence, it is a two-way linked list. It not only implements the list interface, but also implements the dueue interface (double ended queue, which has the characteristics of both queue and stack). Therefore, LinkedList can be used not only as a two-way linked list, but also as a stack and queue.

LinkedList inserts and deletes elements very quickly.

Linkdedlist is also asynchronous. To achieve synchronous access, you can use list = collections synchronizeList(new LinkedList(.....));

(3) Comparison of similarities and differences

(1) ArrayList and LinkedList

1) ArrayList is based on dynamic array and LinkedList is based on bidirectional linked list. 2) ArrayList comparison is applicable to random access (it can be directly indexed, and LinkedList needs to be traversed by pointer); LinkedList comparison is applicable to adding and deleting operations (ArrayList is faster than LinkedList for single insertion and deletion operations, and ArrayList needs to move all subsequent elements for insertion and deletion operations.)

2、 Set interface

Set is a collection that is not allowed to contain the same elements. It maintains its own internal ordering, and random access makes no sense.

（1）HashSet

HashSet is a typical implementation of the set interface. HashSet stores the elements in the set according to the hash algorithm and has good access and search functions. It has the following characteristics:

1) The arrangement order of elements is not guaranteed and may change; 2) HashSet is not synchronized; 3) Collection elements can be empty.

（2）TreeSet

TreeSet is the only implementation of sortedset interface. TreeSet can ensure that elements are in sorting status. TreeSet does not sort according to the insertion order of elements, but according to the actual value. Two sorting methods are supported: natural sorting and custom sorting.

（3）EnumSet

Is a collection class designed for enumeration class. Enumset does not allow null elements to be added. If you try to insert null, a null pointer exception is thrown. The three implementation classes of set are off the shelf and unsafe.

3、 Map interface

Map stores data with mapping relationship. Therefore, two groups of values are stored in the map set. One group of values is used to save the key in the map and the other group is used to save the value in the map. Key and value can be data of any reference type.

The key in the map cannot be repeated, but the value can be repeated. There is a one-way one-to-one relationship between key and value. The unique and definite value can always be found through the specified key.

(1) HashMap and hashtable

HashMap and hashtable are typical implementation classes of map. The relationship between them is similar to ArrayList and vector: hashtable is an ancient map implementation class in jdk1 Appears at 0.

Main differences:

1) Hashtable is a thread safe map implementation, but HashMap is a thread unsafe implementation. The performance of HashMap is higher than that of hashtable. Try to avoid using hashtable. When multiple threads access a map object and ensure thread safety, you can use the methods in collections to turn HashMap into thread safe. 2) Hashtable does not allow null as key and value. If you try to add null to hashtable, a null pointer exception will be thrown.

（2）TreeMap

Treemap is the implementation class of SortedMap, a sub interface of map. Similar to TreeSet, treemap also sorts all keys in treemap based on red black tree, so as to ensure that key values are in an orderly state. Treemap also has two sorting methods:

1) Natural sorting: all keys of treemap must implement the comparable interface, and all keys should be objects of the same class, otherwise ClassCastException will be thrown

2) Custom sorting: when creating a treemap, a comparator object is passed in, which is responsible for sorting all keys in the treemap. Because treemap supports internal sorting, it is usually slower than HashMap and hashtable.

4、 Queue interface

Queue simulates the data structure of queue. Queue is usually a "first in first out" data structure, which usually does not allow random access to the elements in the queue. Common implementation classes of queue: LinkedList and PriorityQueue

（1）LinkedList

LinkedList not only implements the list interface, but also implements the dueue interface (double ended queue, which has both the characteristics of queue and stack). The dueue interface is a sub interface of queue.

（2）PriorityQueue

PriorityQueue saves queue elements not in the order they are added to the queue, but reordered according to the size of queue elements. Therefore, when the peek and poll methods are called to fetch the elements in the queue, the smallest element in the queue is not fetched first. In this sense, PriorityQueue has violated the basic rules of the queue. PriorityQueue does not allow null elements to be inserted.

Summary:

Thread safe vector stack hashtable

Hashtable PriorityQueue enumset is not allowed to insert empty elements

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.