Commonly used data structures in JAVA (java.util.)

There are several commonly used data structures in java, mainly divided into Collection and map There are two main interfaces (interfaces only provide methods, not implementations), and the data structures ultimately used in the program are data structure classes inherited from these interfaces. The main relationships (inheritance relationships) are: (----See java api documentation for details!)

##Collection---->Collections                                                                               Map-----> SortedMap------>TreeMap

Collection---->List----->(Vector \ ArryList \ LinkedList)                                                  Map----- ->HashMap

Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

--------------Collection----------------

1. Collections

API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few others odds and ends.

The methods of this class all throw a

NullPointerException if the collections or class objects provided to them are null.

2、List

API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

The methods of this class all throw a

NullPointerException if the collections or class objects provided to them are null.

List is ordered Collection, use this interface to precisely control the insertion position of each element. Users can use the index (the position of the element in the List, similar to the array subscript) to access the elements in the List, which is similar to Java arrays.

##3、Vector

API---- The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of aVector can grow or shrink as needed to accommodate adding and removing items after theVector has been created. Some functions are convenient for us to use, so it is difficult to avoid the limitations of arrays, and at the same time, the performance cannot surpass arrays. Therefore, where possible, we should use arrays more. Another very important point is that Vector is thread synchronized (sychronized), which is why Vector and ArrayList an important difference.

4、ArrayList
API----Resizable-array implementation of the List

interface. Implements all optional list operations, and permits all elements, including

null. In addition to implementing theList

interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to

Vector

, except that it is unsynchronized.)

Like Vector, it is a linked list based on an array, but the difference is that ArrayList is not synchronized. Therefore, it is better than Vector in terms of performance, but when running in a multi-threaded environment, you need to manage the synchronization of threads yourself.

5、LinkedList

API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (includingnull). In addition to implementing theList interface, the LinkedList class provides uniformly named methods toget, remove andinsert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack,queue, ordouble-ended queue.

LinkedList is different from the previous two Lists. It is not based on arrays, so it is not limited by array performance.
Each node (Node) contains two aspects of content:
1. The data of the node itself;
2. Next node information (nextNode).
So when adding and deleting actions to LinkedList, you don’t have to move a lot of data like array-based ArrayList. This can be achieved by simply changing the relevant information of nextNode. This is the advantage of LinkedList.

List summary:

• All Lists can only hold tables composed of a single object of different types, not Key-Value pairs. For example: [ tom,1,c ]

• ##All Lists can have the same elements, for example, Vector can have [ tom ,koo,too,koo ]

• ##All Lists can have null elements, such as [ tom,null,1 ]

Array-based List (Vector, ArrayList) is suitable for query, while LinkedList is suitable for add and delete operations 6. Set(Interface)

API-----A collection that contains no duplicate elements. More formally, sets contain no pair of elements

e1

ande2 such thate1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematicalset abstraction.

Set is a Collection that does not contain duplicate elements

7、HashSet

## API-----This class implements theSet interface, backed by a hash table (actually aHashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits thenull element.

##Although Set and List both implement the Collection interface, their implementation methods are quite different. List is basically based on Array. But Set is implemented on the basis of HashMap. This is the fundamental difference between Set and List. The storage method of HashSet is to use the Key in HashMap as the corresponding storage item of Set. have a look The implementation of the add(Object obj) method of HashSet can be seen at a glance.

8、LinkedHashSet

## API----Linked list implementation of the

List

interface. Implements all optional list operations, and permits all elements (includingnull). In addition to implementing theList interface, theLinkedList class provides uniformly named methods toget, remove andinsert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack,queue, ordouble-ended queue.

A subclass of HashSet, a linked list.

##9、SortedSet

API---A

Set

that further provides atotal ordering on its elements. The elements are ordered using their natural ordering, or by aComparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering. (This interface is the set analogue ofSortedMap.) Ordered Set,

is implemented through SortedMap. Set summary:

##(1)

The basis of Set implementation is Map (HashMap) (2) The elements in Set cannot be repeated. If you use add(Object obj) method to add an existing object will overwrite the previous object

-------------Map-----------------

Map is a key object A container associated with a value object, and a value object can be a Map, and so on, thus forming a multi-level map. For key objects, like Set, the key objects in a Map container are not allowed to be repeated. This is to maintain the consistency of the search results; if there are two key objects that are the same, then you want to get the value object corresponding to that key object. There will be a problem. Maybe what you get is not the value object you thought, and the result will be confusion. Therefore, the uniqueness of the key is very important and is in line with the nature of the set. Of course, during use, the value object corresponding to a certain key may change. In this case, the last modified value object will correspond to the key. There is no uniqueness requirement for value objects. You can map any number of keys to a value object without any problems (but it may cause inconvenience to your use. You don’t know what you are getting. is the value object corresponding to that key).

1. HashMap

API----Hash table based implementation of theMap interface. This implementation provides all of the optional map operations, and permitsnull values ​​and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

2、TreeMap

API----A Red-Black tree basedNavigableMap implementation. The map is sorted according to to the natural ordering of its keys, or by aComparator provided at map creation time, depending on which constructor is used. It is stored in order, so it has some extended methods, such as firstKey(), lastKey(), etc. You can also specify a range from TreeMap to obtain its sub-Map.

The association between keys and values ​​is very simple. Use the put(Object key, Object value) method to associate a key with a value object. Use get(Object key) to get the value object corresponding to this key object.

#------------illustrate-----------

1. The differences between several commonly used classes
1. ArrayList: Single element, high efficiency, mostly used for query
2. Vector: Single element, thread-safe, mostly used for query
3. LinkedList: Single element, mostly used for insertion and deletion
4. HashMap: The elements are in pairs, and the elements can be empty
5． HashTable: Elements are in pairs, thread-safe, elements cannot be empty
##2. Vector, ArrayList and LinkedList
##In most cases, ArrayList is the best in terms of performance, but when it comes to collections LinkedList will perform better when the elements in it need to be frequently inserted and deleted, but the performance of the three of them is not as good as that of arrays. In addition, Vector is thread synchronized. So:
If you can use an array (element type is fixed, array length is fixed), please try to use an array instead of List;
If there are no frequent deletion and insertion operations, and there is no need to consider multi-threading issues, ArrayList is preferred;

If used under multi-threaded conditions, you can consider Vector;
# #If you need to delete and insert frequently, LinkedList comes into play;
If you don’t know anything, there is nothing wrong with using ArrayList.
#3. Collections and Arrays
exist There are two classes in the Java collection class framework called Collections (note, not Collection!) and Arrays. These are powerful tools in JCF, but beginners often ignore them. According to the JCF document, these two classes provide wrapper implementations (Wrapper Implementations), data structure algorithms, and array-related applications.
I am sure you will not forget the classic algorithms such as "half search" and "sorting" mentioned above. The Collections class provides a wealth of static Methods help us easily complete these annoying tasks in data structure classes:
binarySearch: binary search.
sort: Sort, here is a method similar to quick sort, the efficiency is still is O(n * log n), but is a stable sorting method.

#reverse: Operate a linear table in reverse order. This is a classic test question on data structures in the past!
rotate: "Rotate" the linear table around a certain element as the axis.
swap: Swap the positions of two elements in a linear list.
......
Collections also has an important function It is the "Wrapper", which provides some methods to convert a collection into a special collection, as follows:
unmodifiableXXX: Convert to a read-only collection, where XXX represents six basic collection interfaces: Collection, List, Map, Set, SortedMap and SortedSet. If you insert or delete a read-only collection, an UnsupportedOperationException will be thrown.
##synchronizedXXX: Convert to a synchronized collection.
##singleton: Create a collection with only one element. Here singleton generates a single Element Set,

singletonList and singletonMap generate single-element List and Map respectively.
## Empty set: represented by the static properties EMPTY_SET, EMPTY_LIST and EMPTY_MAP of Collections.

The above is the detailed content of Summarize and share several commonly used data structures in Java. For more information, please follow other related articles on the PHP Chinese website!