Java Improvement Chapter (Twenty)-----Gathering a big family
- 黄舟Original
- 2017-02-10 14:16:55959browse
When writing java programs, in addition to the eight basic data types and the String object, we most commonly use a collection class. Collection classes are everywhere in our programs! There are so many members of the collection family in Java, including the commonly used ArrayList, HashMap, and HashSet, as well as the less commonly used Stack and Queue, the thread-safe Vector and HashTable, and the thread-unsafe LinkedList, TreeMap, etc.!
# The picture above shows The members of the entire collection family and the relationships between them. Below is a brief introduction to each of the above interfaces and base classes (mainly introducing the characteristics and differences of each collection). A more detailed introduction will be explained one by one in the near future.
## 1. Collection interface1. Collection interface is the most basic collection interface. No direct implementation is provided. The classes provided by the Java SDK are all "sub-interfaces" inherited from Collection, such as List and Set. Collection represents a rule, and the elements it contains must follow one or more rules. For example, some allow duplication and some cannot, some must be inserted in order and some have hashes, some support sorting but some do not.
In Java, all classes that implement the Collection interface must provide two sets of standard constructors, one with no parameters, used to create an empty Collection , one is a parameterized constructor with Collection parameters, used to create a new Collection. This new Collection has the same elements as the passed-in Collection.
# 二, List interface
#Interface is the COLLECTION direct interface. List represents an ordered Collection, that is, it uses a specific insertion order to maintain the order of elements. Users have precise control over where each element in the list is inserted, and can access elements based on their integer index (position in the list) and search for elements in the list. The collections that implement the List interface mainly include: ArrayList, LinkedList, Vector, and Stack.
2.1, ArrayList
ArrayList is a dynamic array and is also our most commonly used one gather. It allows the insertion of any element that conforms to the rules, even null. Each ArrayList has an initial capacity (10), which represents the size of the array. As the elements in the container continue to increase, the size of the container will also increase. Each time an element is added to the container, the capacity is checked. When it is about to overflow, the capacity is expanded. So
if we know how many elements to insert, it is best to specify an initial capacity value to avoid excessive expansion operations that waste time and efficiency.
size, isEmpty, get, set, iterator and listIterator operations all run at a fixed time. The add operation runs in amortized constant time, that is, adding n elements takes O(n) time (because of scaling considerations, it's not just as simple as adding elements that has an amortized constant time cost).ArrayList is good at random access. At the same time, ArrayList is asynchronous.
2.2, LinkedList
LinkedList, which also implements the List interface, is different from ArrayList. ArrayList is a dynamic array, and LinkedList is a doubly linked list. So in addition to the basic operation methods of ArrayList, it also provides additional get, remove, and insert methods at the head or tail of LinkedList.
Due to different implementation methods, LinkedList cannot be accessed randomly, and all its operations must be performed according to the needs of a doubly linked list. Operations indexing in a list will traverse the list from the beginning or end (from the end closer to the specified index). The advantage of this is that insertion and deletion operations can be performed in the List at a lower cost. Like ArrayList, LinkedList is also asynchronous. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronized List when creating the List: . So Vector is a thread-safe dynamic array. Its operation is almost the same as ArrayList. ## Stack inherits from Vector and implements a last-in-first-out stack. Stack provides 5 additional methods that allow Vector to be used as a stack. The basic push and pop methods, as well as the peek method, get the element on the top of the stack, the empty method tests whether the stack is empty, and the search method detects the position of an element in the stack. Stack is an empty stack after it is created. # . It maintains its own internal ordering, so random access makes no sense. Like List, it also accepts the presence of null but only one. Due to the particularity of the Set interface, all elements passed into the Set collection must be different. At the same time, attention should be paid to any mutable objects. If e1.equals(e2)==true is caused when operating on the elements in the collection, it must be Certain problems will arise. Collections that implement the Set interface include: EnumSet, HashSet, and TreeSet. is a special Set for enumeration. All elements are enumeration types. HashSet can be called the fastest set to query, because It is implemented internally with HashCode. The order of its internal elements is determined by the hash code, so it does not guarantee the iteration order of the set; in particular, it does not guarantee that the order is permanent. ## Comparator provided when the Set is created, depending on the constructor used. through HashMap Location, it is designed for fast query. It defines a hash table array (Entry[] table) internally. The element will use the hash conversion function to convert the hash address of the element into the index stored in the array. If there is a conflict , then use the form of a hash linked list to string together all elements with the same hash address. You may view the source code of HashMap.Entry, which is a singly linked list structure. keys are sorted by a certain sorting rule, and the internal order is red -black (red-black) tree data structure implementation, realizing the SortedMap interface It is also implemented with a hash table data structure. When resolving conflicts, it also uses the form of a hash linked list like HashMap, but the performance is lower than HashMap Queue, which is mainly divided into two categories, one is a blocking queue, and elements are inserted after the queue is full An exception will be thrown, mainly including ArrayBlockQueue, PriorityBlockingQueue, and LinkedBlockingQueue. Another type of queue is a double-ended queue, which supports the insertion and removal of elements at the head and tail ends, mainly including: ArrayDeque, LinkedBlockingDeque, and LinkedList. Source: http://www.php. cn/ 2, if the number of elements in the collection is greater than the length of the current collection array, the vector growth rate is 100% of the current array length, and the arraylist growth rate is 50% of the current array length. For example When using a relatively large amount of data in a collection, using vector has certain advantages. 1.ArrayList is based on dynamic array The data structure of LinkedList is based on the linked list data structure. 1. HashMap uses hashcode to process its content Quick search, and all elements in TreeMap maintain a certain fixed order. If you need to get an ordered result, you should use TreeMap (the order of elements in HashMap is not fixed). The order of elements in HashMap is not fixed). ## # # 1. Historical reasons: Hashtable is based on the old Dictionary class, and HashMap is an implementation of the Map interface introduced in Java 1.2. # 2. Synchronicity: Hashtable is thread-safe, which means it is synchronous, while HashMap is not thread-safe and is not synchronous. # 7. Selection of sets # 7.1, the choice of list ##1. For random inquiries and iteration operations, the array is compared with all containers than all containers All are fast. Therefore, ArrayList is generally used in random access ArrayList requires element displacement when adding and deleting elements. ##1, HashSet Due to the use of HashCode, it is to some extent. It is said that its performance is always better than TreeSet, especially for addition and search operations. ## 3. Although TreeSet does not have as good performance as HashSet, it still has its uses because it can maintain the sorting of elements.
List list = Collections.synchronizedList(new LinkedList(...)); 2.3, Vector
2.4, Stack
3.1, EnumSet
3.2, HashSet
Based on TreeMap, generate a sorted set is implemented internally with TreeMap. It sorts the elements using their natural ordering, or according to the # 四 四 m ## Map is different from the list, set interface, it is A collection composed of a series of key-value pairs, providing a mapping from key to value. At the same time, it does not inherit Collection. In Map, it guarantees the one-to-one correspondence between key and value. That is to say, a key corresponds to a value, so it cannot have the same key value, but of course the value value can be the same. The implementations of map include: HashMap, TreeMap, HashTable, Properties, and EnumMap.
4.1, HashMap
## 4.2. TreeMap
## 4.3, HashTable
6.1, Vector and ArrayList##
1, vector is thread synchronized , so it is also thread-safe, while arraylist is thread-asynchronous and unsafe. If thread safety factors are not taken into consideration, it is generally more efficient to use arraylist.
3. If you are looking for data at a specified location, the time used by vector and arraylist is the same, both 0(1). In this case, you can use either vector or arraylist. And if the time it takes to move the data at a specified location is 0(n-i) n is the total length, you should consider using linklist at this time, because the time it takes to move the data at a specified location is 0(1), and the query The time it takes to retrieve data at a specified location is 0(i).
## ArrayList and Vector use arrays to store data. The number of array elements is larger than the actual stored data so that elements can be added and inserted. Both allow direct serial number indexing of elements. However, inserting data requires memory operations such as moving array elements, so indexing data is fast and inserting data is slow. Vector uses a synchronized method (thread safety), so its performance is worse than ArrayList. LinkedList uses a doubly linked list for storage, and indexes data by serial number. It needs to be traversed forward or backward, but when inserting data, you only need to record the items before and after this item, so the insertion is faster! 6.2, Aarraylist and Linkedlist
2. For random access to get and set, ArrayList is better than LinkedList because LinkedList needs to move the pointer.
3. For the new and deletion operations add and remove, LinedList has the advantage because ArrayList needs to move data. This depends on the actual situation. If only a single piece of data is inserted or deleted, ArrayList is faster than LinkedList. But if data is randomly inserted and deleted in batches, the speed of LinkedList is much better than that of ArrayList. Because every time a piece of data is inserted into ArrayList, the insertion point and all data after it must be moved. ## 6.3, HashMap and TreeMap
# ##3. Value. : Only HashMap allows you to use null values as the key or value of a table entry.
# 4. Consider ArrayList as the first choice. After all, we only traverse collection elements. Only when the performance of the program is reduced due to frequent insertion and deletion of List, then consider LinkedList ##. #
# 7.2, the choice of SET
## 2. Because TreeMap needs to maintain the order of internal elements, it is usually slower than HashMap and HashTable.