Java.util
Linear List, linked list, hash table is a common data structure, these categories are in java.util package. Collection Interface ├ List │ ├ LinkedList │ ├ ArrayList │ â”” Vector │ â”” Stack â”” Set Map Interface ├ Hashtable public class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable ├ HashMap public class HashMap extends AbstractMap implements Map, Cloneable , Serializable â”” WeakHashMap Collection Interface Collection is a collection of the most basic interface, a representative of a group of Object Collection, Collection of elements (Elements). Collection allow the same number of elements and some not. Some sort while others can not. Java SDK does not provide direct inherited from the Collection of categories, the category Java SDK are inherited from the Collection "of interface" such as List and Set. Collection interface to achieve all categories must be provided two of the constructor function: the structure function parameters used to create an empty Collection, a Collection of the constructor function for the creation of a new Collection, and this new Collection Collection into the same element. After a constructor function allows users to copy a Collection. Traversing the Collection of how each element? Collection regardless of how the actual type, which support an iterator () method, the method returns an iterative son can use the visits to each iteration of every element in the Collection. Typical usage as follows: Iterator it collection.iterator = () / / iteration of a while (it.hasNext ()) (Object obj = it.next (); / /) be the next element from the Collection Interface Two interface is derived and Set List. List List interface is orderly Collection, use this interface to precisely control the location of each element insertion. Users can use index (List elements in the position, similar to the array subscript) to visit the List elements, similar to the Java array. Below and to be mentioned Set different List allows the same elements. In addition to the necessary interface Collection iterator () methods, also provide a listIterator List () method returns a ListIterator interfaces, and standards Iterator interface compared ListIterator with some add () method such as, Allow add, delete, set elements, but also traversing forward or backward. List realization of a common interface LinkedList, ArrayList, Vector and Stack. LinkedList class LinkedList realized List interface allows null elements. In addition to provide additional get LinkedList, remove and insert method in the first LinkedList or tail. LinkedList these operations could be used to stack (stack), the cohort (queue) or two-way Queuing (deque). LinkedList no attention to the synchronization method. If multiple threads at the same time visit a List, it must achieve their visit synchronization. A solution is to create a structure List, synchronized List: List list = Collections.synchronizedList (new LinkedList (…)); ArrayList type ArrayList realized the size of the array variable. It allows all the elements, including null. ArrayList not synchronous. Size, isEmpty, get, set method for run-time constants. But add methods for the apportionment of costs constant, add n elements need to O (n) time. Other methods running time is linear. Each case has a capacity ArrayList (Capacity), which is used to store the size of the array elements. With this capacity can be continually adding new elements to increase automatically, but there is no definition of growth algorithm. When large number of elements need to insert, the insert can be called before ensureCapacity ArrayList method to increase the capacity to improve the efficiency of insertion. And LinkedList, ArrayList is non-synchronous (unsynchronized). Vector Vector type ArrayList very similar, but Vector is synchronized. Vector created by the Iterator, although ArrayList created Iterator interface is the same, but because Vector is synchronized when a Iterator been created and is being used by another thread Vector change the status (for example, add or delete some element), then called Iterator methods will be dished out ConcurrentModificationException, it is necessary to capture the anomaly. Stack of Stack inherited from Vector, the first to achieve a backward the stack. Stack provide five additional approach allows Vector to be used as a stack. Basic push and pop, there are peek method Zhanding elements empty method to test whether the stack is empty, search detected an element in the stack in place. Stack just after the creation of the stack is empty. Set Set is a kind of interface does not include the element of duplication Collection, two elements that arbitrary e1 and e2 have e1.equals (e2) = false, Set up to a null elements. Obviously, the constructor function Set a restrictive conditions, imported Collection parameters can not contain repeated elements. Please note: be careful operation variable object (Mutable Object). If a variable element Set in the state has changed its lead Object.equals (Object) = true will lead to some problems. Map Interface Please note that no successor Map Collection interface, Map provide the key to value mapping. 1 Map can not contain the same key, and each key can map a value. Map interface provides three kinds of pools view, the contents of Map can be set as a key group, a group of value set, or a set of key-value mapping. Hashtable class Hashtable succession Map interface, the realization of a key-value mapping of the hash table. Any non-air (non-null) can be the target of a key or value. Add the use of data put (key, value), get out the use of data (key), the two basic operating expenses for the time constants. Hashtable through initial capacity and the load factor of two performance parameter adjustment. Usually the default load factor 0.75 better achieved the balance of time and space. Increased load factor can save space but find the corresponding time will increase, which will affect as get and put this operation. Hashtable using the following simple example, 1,2,3 put Hashtable, they are the key "one," "two" and "three": Hashtable numbers = new Hashtable (); numbers.put ( "one" , new Integer (1)); numbers.put ( "two", new Integer (2)); numbers.put ( "three" new Integer (3)); To remove a few, such as 2, with the corresponding key : Integer n = (Integer) numbers.get ( "two"); System.out.println ( "two =" + n); as a key target will be calculated to determine the hash function with the corresponding value position, as key to any object, and the need to achieve hashCode equals method. HashCode and equals method inherited from the root Object, if you use the definition of the category as key words, it is necessary to very carefully, in accordance with the definition of the hash function, if the two the same target group, that is, obj1.equals (obj2) = true, their hashCode must be the same, but if two different groups, they are not necessarily the hashCode different if two different hashCode the same object, a phenomenon known as conflict, post-conflict operation hash table will lead to spending time increased, Therefore, as defined hashCode () method, can speed up the operation of hash table. If the same objects have different hashCode, the operation of the hash table will unexpected results (looking forward to the get method returns null), it is necessary to avoid such a problem, one need only remember: at the same time replication methods and hashCode equals, and not only wrote one of them. Hashtable is synchronized. HashMap category HashMap and Hashtable similar difference is HashMap non-synchronized, and allow null, null value and null key. , But will be considered Collection at the HashMap (values () method can be returned to the Collection), the iteration of its operating expenses and HashMap time proportional to the capacity. Therefore, if the performance of iterative important operation, will not HashMap initialization for the high capacity, or low load factor. WeakHashMap WeakHashMap is an improvement of the HashMap, its key implementation of "weak quote," if a key no longer be quoted by the external, then the key can be recovered GC. Summed up the case to the stacks, queues, and other operations, it should be considered List, the need to quickly insert, delete elements LinkedList should be used, if necessary element of fast random access, should use ArrayList. If the program in the single-threaded environment, or visit only one thread, consider such non-synchronized, high efficiency, if multiple threads may also operate a class, the class should be used simultaneously. To pay special attention to the operation of the hash table, as a key to the object of equals and hashCode correct replication methods. As far as possible instead of the actual return to the type of interface, such as the return List rather than ArrayList so if the need arises will be replaced ArrayList LinkedList, client code need not change. This is the abstract programming.
