http://blog.9cbs.net/asklxf/archive/2004/01/06/15992.aspx
Linear tables, linked lists, haveh tables are commonly used data structures. When Java development, JDK has provided us with a series of corresponding classes to implement basic data structures. These classes are in the java.util package. This paper tries to explain the role of each class and how to use these classes correctly by simply description.
Collection├List│├LINKEDLIST│├ArrayList│ └Vector│ └Stack └SETMAP├SHASHTABLE ├STMAP└Weakhashmap
The Collection Interface Collection is the most basic set interface, a collection represents a set of object, ie the element of Collection (Elements). Some Collection allows the same elements and others. Some can sort and others can not work. Java SDK does not provide a class directly inherited from Collection, and the classes provided by Java SDK are inherited from the "sub-interface" such as List and SET. All classes for implementing the Collection interface must provide two standard constructor: None parameters for creating an empty collection, a constructor with a Collection parameter is used to create a new Collection, this new Collection and biography Into Collection has the same elements. The latter constructor allows the user to copy a collection. How to traverse each element in Collection? Regardless of the actual type of Collection, it supports a method of Iterator (), which returns an iteration, using this iteration to access each element in the Collection one by one. Typical usage is as follows: Iterator it = Collection.iterator (); // Get an iterative while (it.hasnext ()) {Object Obj = it.next (); // Get the next element} derived by the Collection interface The two interfaces are LIST and SET.
The List interface list is an ordered Collection that can accurately control the insertion of each element using this interface. Users can use an index (the location of the element in LIST, similar to the array subscript) to access the elements in the list, similar to the number of Java. Unlike the SET to be mentioned below, List allows the same elements. In addition to the Iterator () method with the Collection interface, List also provides a listiterator () method, returning a listiterator interface, compared to the standard Iterator interface, the Listiterator is more than some add () methods, allowed to add, Delete, set the element, but also traverse forward or backward. Realize the common class of List interfaces with LinkedList, ArrayList, Vector and Stack.
LinkedList class LinkedList implements a List interface, allowing NULL elements. In addition, LinkedList provides additional GET, REMOVE, and INSERT method in the head or tail of LinkedList. These operations allow LinkedList to be used as a stack, queue, or a two-way queue (DEQUE). Note that LinkedList has no synchronization method. If multiple threads accesses a list, you must implement access synchronization yourself. One solution is to construct a synchronized list: list list = collections.synchronizedlist (New LinkedList (...)); ArrayList class ArrayList implements a variable size array. It allows all elements, including NULL. ArrayList is not synchronized. Size, ISEMPTY, GET, and SET methods run time are constants. However, the ADD method is overhead as a constant of the distribution, and the time to add N elements that require o (n). Other method run times is linear. Each ArrayList instance has a capacity, that is, the size of the array for storing the element. This capacity can be automatically increased as new elements continue, but the growth algorithm is not defined. When you need to insert a large number of elements, you can call the EnSureCapacity method before insertion, you can increase the capacity of ArrayList to increase the insertion efficiency. Like LinkedList, ArrayList is also unsynchronized.
VECTOR class Vector is very similar to ArrayList, but the vector is synchronized. Iterator created by Vector, although Iterator created with ArrayList is the same interface, but because the vector is synchronized, when an Iterator is created and is being used, the other thread changes the status of the Vector (for example, add or delete some Element), when you call the method of Iterator, the ConcURRentModificationException will thus be thrown, so the exception must be captured.
The Stack class stack inherits from the vector to implement a stack of a backward first. STACK provides 5 additional methods such that the vector is used as a stack. Basic PUSH and POP methods, as well as the PEEK method to get the elements of the top of the stack, the EMPTY method tests whether the stack is empty, the Search method detects the position of an element in the stack. Stack is just after being created.
Set Interface Set is a collection that does not contain duplicate elements, that is, any two elements E1 and E2 have E1.Equals (E2) = false, and SET has a NULL element. Obviously, the SET constructor has a constraint, and the incoming Collection parameter cannot contain a repeated element. Note: You must be careful to operate the variable object (Mutable Object). If the variable element in a set changed its own state, it will result in object.equals (object) = true.
Map interface Please note that MAP does not inherit the Collection interface, and the MAP provides key to value mapping. The same key can not contain the same key, each of which can only map a value. The MAP interface provides three sets of views, and the contents of the MAP can be treated as a set of Key collections, a set of value collections, or a set of Key-Value mappings.
HashTable class hashtable inherits the MAP interface to implement a Hach-Value mapping hash. Any non-null object can be used as a key or value. Add data Using PUT (Key, Value), remove the data using GET (KEY), the time overhead of these two basic operations is constant. HashTable Tuninescence through the INITIAL CAPACITY and LOAD FACTOR. Usually the default Load Factor 0.75 excellent time and space balance. Increasing the Load Factor can save space but the corresponding lookup time will increase, which affects operations like get and PUT. With a simple example of using HashTable, put 1, 2, 3 in Hashtable, their Key is "one", "two", "three": Hashtable number = new hashtable (); NumBers.put ("one" , New Integer (1)); NumBers.Put ("Two", New Integer (2)); NumBers.Put ("Three", New Integer (3)); Take a number, such as 2, with the corresponding Key : Integer n = (Integer) Numbers.get ("Two"); System.out.println ("Two =" N); Since the object as a key will determine the Value corresponding to the hash function Location, therefore any object as a Key must implement a HashCode and Equals method. Hashcode and Equals methods inherit from the root object, if you use a custom class as a key, be quite careful, follow the definition of the hash function, if the two objects are the same, ie obj1.equals (obj2) = true, then Their HashCode must be the same, but if the two objects are different, their hashcode is not necessarily different. If the two different objects of HashCode are the same, this phenomenon is called conflict, and the conflict will result in an increase in the time overhead of the operation hash. So try to define the HashCode () method to speed up the operation of the hash table. If the same object has a different HashCode, the operation of the hash table will have unexpected results (the expected GET method returns null), to avoid this problem, just keep in mind: To copy the equals method and havehcode method, Not only to write one of them. Hashtable is synchronized. HashMap class HashMap and HashTable are similar, and the HashMap is non-synchronous and allows NULL, NULL VALUE, and NULL KEY. However, when HashMap is treated as a Collection (VALUES () method can return to Collection, its iterative subsystem is overhead, and the capacity of HashMap is proportional. Therefore, if the performance of iterative operation is quite important, do not set the initial capacity of HashMap, or Load Factor is too low.
WeakhashMap class WeakhashMap is an improved HashMap that implements "weak references" for Key, if a key is no longer referenced outside, then the key can be recycled by GC.
Summary If it is involved in stacks, queues, etc., consider using List, for quick plug, delete elements, should use LinkedList, if you need to quickly random access, you should use ArrayList. If the program is in a single threaded environment, or the access is only in one thread, considering the non-synchronous class, its efficiency is high, if multiple threads may operate a class at the same time, the synchronous class should be used. Pay special attention to the operation of the hash table, as a key to Key, to properly reply Equals and HashCode methods. Try to return to the interface instead of the actual type, if you returns List instead of arraylist, the client code does not have to change when you need to change ArrayList to linkedList. This is for abstract programming. (Reference: Sun JDK1.4.1 API DOC)
