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
└SET
Map
├Hashtable
├Hashmap
└weakhashmap
COLLECTION interface
Collection is the most basic set interface, a collection represents a group of object, ie the Collection element (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
}
The two interfaces derived from the Collection interface are List and SET.
List interface
List is an ordered Collection, using this interface to accurately control the position of each element insertion. 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 when creating a list:
List list = collections.synchronizedlist (New LinkedList (...)); ArrayList class
ArrayList implements an array of variable sizes. 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.
Stack class
STACK inherits from the vector to achieve a backward first stack. 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 maximum of NULL elements.
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
Note that Map does not inherit the Collection interface, and the MAP provides mapping of Key to Value. 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 mapped hash table. 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 NumBers = new hashtable ();
NumBers.Put ("One", New Integer (1));
NumBers.Put ("Two", New Integer (2));
NumBers.Put ("Three", New Integer (3));
To 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 location of the corresponding value by calculating its hash function, any HashCode and Equals methods must be implemented as a key to Key. 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 havehtable are similar, and the difference is that HashMap is non-synchronized and allows null, namely 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 reference" to Key, if a key is no longer referenced outside, then the key can be recycled by GC.
to sum up
If you are involved in stack, queue, etc., you should consider using List, for quick plug, delete elements, you should use LinkedList, if you need to quickly access elements, 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)
