?
Collection and general collection?
??
Gong Yongsheng (gongys@lenovo.com) July 2003
This article describes the Jakarta project Commons-Collection, and its current version is version 2.1. This article is a collection and example example of the J2SDK collection framework. Examples can greatly speed up the programmer familiarity and use, although the examples in the article do not cover all interfaces but exhibit the use of the main concepts of the collection. The legacy issues and summary parts can further deepen the readers' understanding of the entire collection framework to promote the use and development of Commons-Collection.
1. Project vision implementation and improvement of a basic class library that handles set data structures. 2. User problem programmer often spends more time in the development program, and the collection structure of the collection is not standardized, the function is not comprehensive, there is a set of data structures with ready-to-art collection to greatly improve the development speed and Software quality. 3. Simple analysis of common collection data structures include the following: (1) SET-guaranteed members unique, support collection operations in mathematics, such as pay, and; (2) List-support member order, provide access to members by index; (3) MAP-member is a key value, provide button object search value object; (4) BAG-retains member, can query members' quantity; (5) Queue - support advanced first, can expand to press priority Operation; (6) stack-supports first out. ? 4. Using the interface 4.1.j2dk Collection Framework Description "JDK1.4 Collection Framework Structure Diagram" shows the J2SDK collection framework class structure. The J2SDK collection is taken by the Collection interface, SET, LIST, and MAP bear the protagonist, with data structure Tree, Array, Hash, Link as a specific implementation means, which constitutes a fairiant framework in functions and performance. The entire framework consists of the main structure and the auxiliary structure, and the body structure forms a framework basis, and the auxiliary structure is convenient for the use of the frame. 4.1.1. Structural Structure We use the following table to describe the main structure of the J2SDK's collection framework:
Interface Brief Remiction Implementation Operation Feature Member Requirements SET Members You cannot repeat the outside of the Hashset dissemination. Members can be objects of any Object subclass, but if the equals approach is covered, pay attention to modify the HashCode method. The outside of the Treset is in an orderly manner; additional implementation members of SortedSet, support subset, requires the Caparable interface, or use the Comparator constructed TreeSet. Members are generally the same type. LINKEDHASHSET External Press Sequence Traversing Member Member and Hashset Members Similar List Provides Random Access ARRAYLIST, which is a random access based on index, providing fast index-based member access, adding and deleting support for tail members to arbitrarily Object Objects LinkedList for members of any location in the list is better, but to the index-based member access support performance can save key values for any Object subclass, based on key-based Operation, Compareto or Compare method to the key sorting HashMap can meet the universal requirements key members of the user to the MAP can be an object of any Object subclass, but if the equals method is covered, pay attention to modify the HashCode method. TreeMap supports the keys to be sequentially traversed, and it is recommended to use HashMap to increase and delete members, and finally generate TreeMap from HashMap; additionally implementing the SortedMap interface, the support sub-MAP, the operation key member requests to implement the Caparable interface, or use Comparator Construct TreeMap. Key members are generally the same type. LINKEDHASHMAP reserved insertion order, use the equals method check key and value of equal sexy members can be objects of any Object subclass, but if the equals method is overwritten, pay attention to modify the HashCode method. IdentityHashMap uses == to check the equality of keys and values. Members use strict equal weakhashmap their behavior depends on garbage collection threads. There is no absolute reason to use less? 4.1.2. Auxiliary structure In the J2SDK collection framework, there are some operations and some operations in addition to specific implementations Assisted classes, including a FA? ADE class, two equivalents, and two comparison interfaces. The FACADE class -collections class Collections class contains universal operations in the framework, which acts as Fa? ADE. These operations are implemented as static functions, divided into several classes:?
Maximum smallest function, for a collection, find the largest minimum member (or key member), require members to implement the Comparable interface; generating an uncharged Singleton collection (Singleton collection is a collection containing a member); sort LIST, restructuring , Reverse operation; fill the List, batch replacement, and fast search operation; synchronize the collection to adapt to the multi-threaded environment; the collection is not changed to the collection, returning the collection view of the unchargeable. ? Equal method one - Equals (Object O) method equals method implements a equivalent relationship:?
Deflex: For any object x, x.equals (x) must return true; symmetry: For any object x and y, x.equals (y) == True is only when Y.Equals (x) == True; Transmissionability: For any object x, y, z, if x.equals (y) == true and y.equals (z) == True, x.equals (z) == true; consistency: for Any object x and y, as long as there is no modification of X, Y, multiplex iequals (y) calls should return the same value; for any Non-Null object x, x.equals (null) == false. • This method in the Object class is implemented strict equal, that is, if the two objects are the same object, ie == operation is true, returns TRUE. So if you want to search for a member object such as content or such a collection of content or a key mapped in the Map, you must override the Equals (Object O) method. Equal Method 2 - Hashcode () Method This method returns an object's HASH code, in a collection of HashTable data structures, it determines which bucket in which this object is placed in. The Equals method is the basis for further to BUCKET to find specific objects. For the HashTable data structure, the General Protocol of the HashCode method is that the equals method is the same as the integer () returned to the equal two objects. This object can only be found in the HashTable data structure. The integer () returned by the equals method is not equal to the two objects of the unequal, if the same is the same conflict. So try to ensure that the Equals method is not the same as the integer returned to the unhelax object. The internal address of the class Object implemented use object is converted to an integer returns, making O1.Equals (O2) when and only when O1.hashcode () == O2.hashcode (). Comparison Interface One - Interface Comparable This interface requires full order, also called nature, and the COMPARETO of this interface is called a natural comparative method. The collections.sort method can automatically sort a list of objects that implements this interface class. In the case where there is no Comparator, such an object can also be used as a member of the sorting MAP or a member of the SET. If any two instances E1 and E2 of a class, (E1.Compareto ((Object) E2) == 0) and E1.Equals ((Object) E2) have the same logical value, we say this class's natural sort Unanimously equally. In addition, E1.Compareto (NULL) should throw NullPointeredException. Strong requirement to maintain this consistency, otherwise the sorting set (or MAP) that specifies the specified Compare will destroy the SET (or Map) universal interface protocol because these interface protocols determine the member identity with the Equals method. The agreement of the CompareTo method is:?
When E1
When E1
Copy the ready collection; perform a modification operation on the replica; overwrite the ready-made collection with a replica. • When the program runs in a single-threaded environment, we should use Java.util.Arraylist directly. CursorablelinkedList's double-strand implementation of the List interface implements all optional operations of the LIST interface, including the Stack / Queue / Dequeue operation in LinkedList, and supports Listiterator, allowing concurrent modifications to LIST. CursorableSublist is an internal class. 4.2.3.Map Collection "General Collection MAP" diagram shows the expansion of the Commons-Collection to the JSDK collection framework, it can be said to be a huge lineup. The first is the FAST version of HashMap and TreeMap. About the Fast version can see the description of the FastArrayList in front. Beanmap is a very interesting map. It uses Java Bean's attribute reflection function to turn a Java bean into a map, such as BeanMap with a bean structure with the Name property, you can use BeanMap.Get ("Name") to get bean Name attribute value. ReferenceMap is a HashTable-based MAP implementation that allows the garbage collection thread reclaim key value mapping. When you create a ReferenceMap object, you can specify a category (Hard, Soft, or Weak) of the key, when you create a collection with a non-HARD reference, the garbage reclaimed thread may reclaim these keys or value objects when the bile or value is not reachable. When the reference species of the key is "WEAK", the value of the reference species is "hard", the behavior of ReferenceMap is similar to WeakhashMap in the J2SDK collection framework. ReferenceMap defaults to use the "hard" reference to the key and "Soft" reference . SoftRefhashMap is replaced by default constructed. MultihashMap implements the MultiMap interface. MultiMap is slightly distinguished from ordinary MAP, and the key value mapped in the key value is a collection. For example, execute PUT (Key, New Integer (1)), execute the Object Get (KEY) will get a collection of integers. That is, this class does not cover the value objects corresponding to the previous same key, but to add the new value object to the value of the value corresponding to the key. DoubleRedMap is a red-black tree implementation of a MAP interface. This class guarantees the double sort of the key object and the value object. This class is very valid for the program that needs to find the key-value object by the key object or value object, and the ordinary MAP implementation can only pass the key object check button - value pair. Although the same purpose can be implemented with a pair of TreeMaps (the ContainSKey method is implemented by the key value Treemaps, the ContaSvalue method is implemented by another value button TreeMaps), which is prone to problems on both TreeMaps data synchronization, and redundant data is relatively large . The DoubleRedMap implemented by the red-black tree is easy to synchronize data, and redundancy is minimized. This class has some restrictions on data members: if a value or key already exists in a DoubleRDeredMap object, try saving this value or button to throw an ILLEGALARGUMENTEXCEPTION exception. The Map.Entry instance returned by this class is not allowed to call the setValue () method. In order to operate the DoubleRedMap object, this new method is as follows:?
Object GetKeyForValue (Object Value) is an opposite side of the GET method of the normal MAP, which is specified from the value. Object RemoveValue (Object Value) Looks and delete the specified value object and returns the key object corresponding to this value object, and this key object does not exist in the DoubleRedMap object. Set entrysetByValue () Returns a Value object sorted Map.Entry collection. Set KeySetByValue () Returns a key object sorted Map.Entry collection. Collection ValuesByValue () Returns a value of values for a value object sort. PROXYMAP is a Wrapper implemented to the map. Its MAP method is directly called by the WRAP Map. This class is generally used as an extended framework for extension of the existing MAP implementation, which is not very convenient to inherit. SequencedHashMap is a MAP implementation in the key value for insertion sequence, which has an operating interface similar to the list, except for getFirst, GetLast method access to the head member, or even based on index random access keys and value objects. This is the characteristic of LinkedHashmap in the J2SDK collection frame. LRUMAP is a subclass of sequencedhashmap with a maximum size. When the number of members in the collection reaches the maximum size, the recent least use algorithm is used to exclude members. All operations to a key object (regardless of GET or PUT) are moved to the front end. The last MAP we want to introduce is staticbucketmap. This class implements HashMap used in a multi-thread environment, but the number of barrels of this class is specified in the constructor and will not change. There are independent concurrent access monitor (Monitor) for each barrel, so multiple threads can access different buckets. This class itself is a thread safe, and does not require a Collections.SynchronizedMap (MAP) method to get the synchronization version. When using this class, you should pay attention to the uncertainty of batch operation results under multi-threaded environments. 4.2.4. Buffer Collection "Buffer Buffer" Figure shows that Commons-Collections is another concept for the J2SDK Collection Framework Extension. ArrayStack is a stack API that extends ArrayList, which is appropriate to operate at a single thread. The deletion order of a member in an ArrayStack object is based on its insertion sequence: the most recently inserted first deletion, and its Iterator is accessed by insertion. The object of the BoundedfiFobuffer class represents a buffer with fixed size, the member's deletion is consistent with their insertion order, ie "advanced first". You can get the Synchronous version of the BoundedFiFobuffer class object by the following functions: buffer fifer (new boundedfifer (new boundedfifer ()); UNBoundedFiFobuffer is the same function as the BoundedFiFobuffer class, but buffer size can be expanded at runtime. Synchronous objects of their objects can also be obtained by bufferutils: buffer fifer (new unboundedfifo ()); binaryHeap is a ferrule implementation for PriorityQueue and Buffer. Deleting an operation is deleted is a member (minimum member or the biggest member) of the top, and the order of members of Iterator is uncertain.
Synchronous objects of its objects can be obtained by bufferutils: buffer heap = bufferutils.synchronizedbuff (new binaryheap ()); SynchronizedPriorityQueue is a wrapper of a thread secure PriorityQueue class, and the method is a multi-threaded security decoration of the packaged method. 4.3. Application Programming Interface The following figure shows the application programming interfaces of various sets, and additional interfaces There are also various Iterator, Utils classes, and a particularly implementable class expansion interface, see the relevant documentation. Understanding the best way to get a collection interface is to read the document, especially to see the impact of these interface functions on collections and return values. 4.4. Example 4.4.1. Material For the purpose of demonstrating the collection, we first prepare two members object classes and a Comparator implementation. The following table describes the implementation of two member object classes on the auxiliary structure in the collection framework (Note that the equals method and the HashCode method must match the relationship of the above secondary structure section): "Class name Equals method and havehcode method MyBean does not override MYBean_comparable overlay MyBeanComparator implements two object sorting algorithms for Tree structure implementation? MyBean code is as follows:
Public class mybean {
PRIVATE STRING NAME;
Public mybean (String name) {
THIS.NAME = Name;
}
Public mybean () {
Super ();
}
Public string getname () {
Return Name;
}
Public void setname (String string) {
Name = string;
}
}
MyBean_comparable code is as follows:
Public class mybean_comparable imports comparable {
PRIVATE STRING NAME;
Public mybean_comparable () {
Super ();
}
Public mybean_comparable (String Name) {
THIS.NAME = Name;
}
Public string getname () {
Return Name;
}
Public void setname (String string) {
Name = string;
}
Public Int hashcode () {
Return name.hashcode ();
}
Public Boolean Equals (Object Arg0) {
Try {
MyBean_Comparable Pt1 = (MyBean_comparable) arg0;
Return getName (). Equals (pt1.getname ());
} catch (classcastexception e) {
Return False;
}
}
Public int compareto (Object arg0) {
Try {
MyBean_Comparable Pt1 = (MyBean_comparable) arg0;
Return getName (). Compareto (pt1.getname ());
} catch (classcastexception e) {
Return 0;
}
}
}
The MyBeanComparator class implements the Comparator interface:
Public class mybeancomparator imports comparator {
Public Int Compare (Object E1, OBJECT E2) {
Try {
MyBean Pt1 = (MyBean) E1;
MyBean PT2 = (MyBean) E2;
Return pt1.getname (). Compareto (pt2.getname ());
} catch (classcastexception e) {
Return 0;
}
}
}
4.4.2. Example of example code mainly reflects the main features of the collection in the framework, as follows:
Import java.util.collection;
Import java.util.hashmap;
Import java.util.Identityhashmap;
Import java.util.iterator;
Import java.util.list;
Import java.util.map;
Import org.apache.commons.collections.bag;
Import org.apache.commons.collections.fastarrayList;
Import org.apache.commons.collections.hashbag;
Import org.apache.commons.collections.treebag;
Public class collectest {
Public static void main (string args []) {
//experiment one
System.out.println ("Test BAG Features");
Testcount ();
// Experiment 2
System.out.println ("Test Comparator Interface");
Testcomparator ();
// Experiment three
System.out.println ("References for Test Members");
TestReference ();
// Experiment four
System.out.println ("The meaning of the collection of not changed");
Testunmodified ();
// Experiment five
System.out.println ("Test FastArrayList");
TestfastList ();
// Experiment 6
System.out.println ("Strict Equivalence" of Identityhashmap);
Testidentityhashmap ();
}
/ **
* Main display:
* 1, the collection of HASH structures can contain any member;
* 2, BAG reserves the number of members;
* /
Private static void testcount () {
Bag baghash = new hashbag ();
Baghash.Add (New MyBean ("MyBean");
Baghash.Add (New MyBean ("MyBean");
Baghash.Add (New MyBean_comparable ("MyBean_Comparable1"));
Baghash.Add (New MyBean_comparable ("MyBean_Comparable1"));
Baghash.Add (New MyBean_comparable ("MyBean_Comparable2"));
System.out.println ("TestCount (havehbag) =" baghash);
}
/ **
* Mainly showing Comparator to write and TreeBAG sequential characteristics
*
* /
Private static void testcomparator () {
INT i = 0;
Bag Bagtree = New Treebag (New MyBeanComparator ()); Bagtree.Add (New MyBean ("SECOND"));
Bagtree.Add (New MyBean ("first");
Bagtree.Add (New MyBean ("first");
Iterator itrator = Bagtree.Item ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
System.out.println ("Testcomparator (Treebag) =" Element);
}
Iterator = Bagtree.iterator ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
ELEMENT.SETNAME ("Name" i );
System.out.println ("TestComparator (Treebag) =" Element.getName ());
}
Iterator = Bagtree.iterator ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
System.out.println ("Testcomparator (Treebag) =" Element);
System.out.println ("TestComparator (Treebag) =" Element.getName ());
}
System.out.println ("TestComparator (Treebag) =" Bagtree);
}
/ **
* Mainly displaying the characteristics of the collection reservation reference
*
* /
Private static void testreference () {
Bag Bagtree = New Treebag (New MyBeanComparator ());
MyBean mybean = new mybean ("before");
Bagtree.Add (MyBean);
System.out.println ("Testreference (Bagtree) =" Bagtree);
Iterator itrator = Bagtree.Item ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
System.out.println ("TestReference (Bagtree) =" Element.getName ());
Element.setname ("after");
}
Iterator = Bagtree.iterator ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
System.out.println ("TestReference (Bagtree) =" Element.getName ());
}
System.out.println ("TestReference (Bagtree) =" Bagtree);
/ **
* Mainly displaying the meaning of uncommitted collection
*
* /
Private static void testunmodified () {
Bag baghash = new hashbag ();
Baghash.Add (New MyBean ("first");
Baghash.Add (New MyBean ("first");
INT i = 0;
Collection c = java.util.collections.unmodifiableCollection (Baghash);
Try {
C.ADD (New MyBean));
} catch (unsupportedOperationException e) {
System.out.println ("Testunmodified: Yes It Cannot Be Modified!");
}
Iterator iterator = c.iterator ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
System.out.Println ("Testunmodified (Before) =" Element.getName ());
ELEMENT.SETNAME ("Forth" i );
}
Iterator = c.iterator ();
While (item.hasnext ()) {
MyBean Element = (MyBean) iterator.next ();
System.out.println ("Testunmodified (after) =" Element.getName ());
}
}
/ **
* Test the characteristics of FastArrayList
* /
Private static void testfastlist () {
ArrayList (1000);
FastList_slow (1000);
FastList_fast (1000);
}
Private static void arraylist (int accesss) {
List list = new arraylist ();
Long Start;
Long end;
Start = system.currenttimemillis ();
For (int i = 0; i
This example code not only allows us to understand the characteristics of the BAG collection in general collection, but also let us understand the important structure of the entire collection framework.
Experiment One - Test the characteristics of the BAG as follows:
Testcount (havehbag) =
[2: mybean_comparable @ 123d5a54, 1: mybean_comparable @ 123d5a55, 1: mybean @ 13e8d89, 1: mybean @ b8df17]
Indicates that there are 3 MyBean_Comparable objects in this BAG, two of which; there are two different MyBean objects. From the test material, the MyBean does not cover the Equals and HashCode methods, so inherits the strict equalization of Object, so the two MyBean objects in the BAG collection are the same, but they are different objects that are different, so BAG thinks them. not equal. On the other hand, although the 3 MyBean_Comparable objects are not strict, the MyBean_comparable class covers the equals and hashcode methods, making it equal to whether the names of the two objects are equal. Experiment 2 - Test the output of the Comparator interface is as follows: Testcomparator (Treebag) = first
TestComparator (Treebag) = Second
TestComparator (Treebag) = Second
Testcomparator (Treebag) =
[1: mybean @ 10385c1, 2: mybean @ 42719c]
Although the MyBean object called Second is earlier than the object object, the output is after, it indicates that the Treebag implemented by the TREE data structure is saved in order. In addition, we joined a MyBean_comparable object called Third in the Treebag in the experiment, but showed a MyBean object called Second, which is because we implemented the Compare method of the Compare is not the object of the Mybean class. . When the MyBean_Comparable object called Third is joined, the joining algorithm is compared to the first added object, so it is simply added to the count of MyBeaan object named Second, and throws myBean_comparable objects. . From this test, it can also be obtained: BAG is only a copy of the object that is considered equal. Test three - test members' quotation outputs are as follows:
TestReference (Bagtree) = [1: mybean @ 1e5e2c3]
TestReference (Bagtree) = Before
TestReference (Bagtree) = after
TestReference (Bagtree) = [1: mybean @ 1e5e2c3]
The test results show that the collection is stored in the collection, because modifying the member object, it is reflected in the collection. Experimental four - meaning output of uncomfortable collections is as follows:
Testunmodified: Yes it cannot be modified!
Testunmodified (Before) = first
Testunmodified (Before) = first
Testunmodified (after) = forth0
Testunmodified (after) = forth1
The results indicate that the collection of collections. UNMODIFIABLECOLLECTION method does not allow adding or decrease, but it is not possible to avoid members to be modified, which is associated with the reference nature of the tested four. Experiment five - Test FastArrayList's characteristic output should be determined based on the number of members tested. For a large set of members, the Clone operation in the FAST mode may be a performance bottleneck, making the performance possible below FastArrayList that has been in Slow mode, but FastArrayList should be more reflected in multithreaded environments. Experiment six - Test the strict equalization output of Identityhashmap is as follows:
Identityhashmap: True
Identityhashmap: False
Hashmap: True
Hashmap: True
Indicates that the judgment of the IdentityHashMap is strictly equal, that is, the two key objects are when the same memory object is equal, that is, the same NEW operation is generated. 5. Internal analysis of the main data structure and algorithm, you can find related books to further understand the algorithms in the source code, this article is no longer redundant. 6. The remains of the legacy problem, the Commons-Collection is more perfect for the J2SDK collection framework in multithreading, collection type, implementation method, etc., if there is a special demand, can expand the collection framework according to your needs. The more obvious legacy problem is that some functions on the implementation code of Commons-Collection does not follow the J2SDK collection framework protocol, which may result in inconsistencies on code behavior. The problem in design may not follow the principle of interface becoming, because some of the implementation of an interface expands the scope of the interface, such as the SETFAST method in FastArrayList is not in the List interface, but this method is using a FastArrayList collection Key way. 7. Summary Use Collection is the programmed problem we often encounter, and the accurate understanding of the J2SDK collection framework and Commons-Collection's extension of this framework help to improve our work efficiency. Use these collection classes to pay attention to their performance and constraints in multithreaded environments, and examples about the collection of multi-threads can look for StandardSession to the implementation of the Attribute collection in the Tomcat source; another important aspect is to choose the right requirements. Functional collection class, because the increase in functions often means a decline in performance. If the J2SDK's collection class and the Collection class of the Commons-Collection cannot meet the needs, the reader can also design and implement itself, such as implementing a collection of truly unable to change. Another problem that the reader needs to pay attention to is the processing of each collection to the NULL value. 8. Reference information Java.sun.com There is a set of various set selection on various set selection. Java.sun.com website The explanation of the example references of various implementations on the website, in addition to finding the Java specification, you can see "Java Pitfalls Chinese version" Item 11
About the Author
?
Gong Yongsheng Email: Gongys@lenovo.com Address (AddR): Lenovo, No.7 Kondow Road, Shangdi Information Industry Base, Haidian District, Beijing: 100085 Phone (TEL): 010-62986638-5749 Mobile (Mobile): 13910304330 Fax (Fax : 010-62975824
