For Java Collection Framework (JAVA Collection, Java), Java players are probably unfamiliar, and similar concepts in C are Standard Template Library, STLs, mainly for some data structures and related algorithms. Considering this is a tool that Java beginners will always contact, so there are some of the following texts. Mainly referred to
A tutorial on IBM DeveloperWorks
It may explain more clear, here is concentrated, the real coming dragon can look at the JDK document ""
The Collections Framework
", Illustrate more detailed.
Source of the problem
Collection: The object's container and data structure recalls that we may face something in program design, nothing more than two categories: basic types and composite types, the latter commonly organized way is class. Unlike basic types, class objects usually need to be allocated with dynamic mode, such as a NEW in memory, and this OO program will inevitably use. At the same time, we face more than just a single basic type or object, what is the organization mode usually used for multiple such data? Nice, it is an array, which is an old concept with the program design. The advantages of the array are obvious, such as operations such as the subscriber retrieval element, but the disadvantages are also obvious: space fixation cannot be dynamically increased (inserted or sensitive to the array of borders like Java), insert or Delete elements are more laboriest. Therefore, the array is not a convenient tool for solving all collection problems. We may need some new tools to study these tools are often research.
The data structure, especially, the array itself is a linear ordered data structure.
The mathematical foundation of the data structure is
Collection, why do you say this? Say above, now we have to study is not a single basic type or object, is it a collection of multiple objects? From the OO perspective, the collection is also an object, but it is a special object: the object's container (note that we have not continued to discuss the collection of basic types, because the basic type and storage allocation is in nature of the object difference). A fundamental question of the collection is: given an element, the collection must be able to answer the element or not this collection. There is also a problem is also very important, that is: if the element belongs to a collection, the position of this element should be unique, or it is
Uniquely determined. Of course, there are other problems, such as finding, traversal, sorting, etc., which are related to specific collection types, will later.
No content, ordered, mapping to talk about the type of collection, our collection concept in high school is one of them, called "
Unordered ", that is, the various elements of the collection are equal, there is no secondary difference, so they will never allow an exproportionate element in the unknown set, otherwise, when this element is taken, I don't know if I should take it. Which one, this violates the above "unique determination" principle.
Wait until we got a university and started to know another collection type, called "
Ording set "(or" linear table ", distinguishing a non-linear data structure like" tree "," map "in the future), if it is a computer professional, the algebra of discrete mathematics "Structure", then you know more, "Order" is actually a "binary relationship", which is exactly "bias relationship", which can contain the same element because two same elements The "serial number" can be different, so that the "serial number" can still "uniquely determine" an element, an array is another feature of an ordered set is that any two elements can determine their order. Distribution set Ordain, there is a third possibility? Oh, it still appears in our high school algebra textbook, called "
Mapping ". Mapping is also a collection? ,or
Google "Collection On Paradox"). The mapping is actually a collection of "element pairs", just like
f (a) = b, f (c) = d, ... equivalent to collection (no sequence set)
{(A, B), (C, D), ...}, can be seen as a collection of (original icons, icons) in "mapping", in turn, is (keyword key, value value) set. So we can draw a beautiful function image on the Cartesian orthogonal coordinate plane, because in the view, the function (mapping) is a point on the two-dimensional plane, understand? In this way, "Ordered Set" is also understood, the prejudice relationship is
A> b> c> d> ... (I don't know "predecessor relationship" as an array
X [1] = a, x [2] = B, X [3] = C, X [4] = D ... well) equivalent to disorder set
{(1, a), (2, b), (3, c), (4, d), ...},,, all the sets are equivalent to the unordered set! So just taught us a collection, huh, huh ...
JCF's family is good, these we all know that it is not in mathematics lessons, saying so much nonsense, why didn't I pull it? JCF's shadow I haven't seen it yet! The list is to see the official, this will come to you. In fact, the above concept is very important to understand JCF. JCF is a very large-scale family. Look at its class level, you know, the following picture (Figure 1) is taken from the famous Thinking in Java: Figure 1 JCF hierarchy Wow, so many interfaces and classes are really a bit It is a feeling that people can't get started. In fact, we really need to remember the structure of such a super-ultrasy (Figure 2): Figure 2 This picture looks comfortable? But what is it possible? How can it grasp the entire JCF? We put the Collection interface on top, meaning that you want to say: Collection is actually a "ancestral" in the JCF family, almost all JCF members are derived from the interface, or have a close relationship with it, and Collection provides on the collection Some generic operations interface, including insertion (ADD () method), delete () method, determining an element is not its member () method), traversal (Iterator () method), and more. Note that the previous "nonsense" will be reflected here: the SET interface reflects the concept of "unordered set". It does not allow repeating elements to appear; the List interface represents "Order"; and the MAP interface Yes "Mapping" (in the early Java version, we will see later), in fact, the Map.Entry interface is representing a "element pair" we can get this by the Entryset () method " Element pair consisting of SET objects. We noticed that SET and LIST were derived from "ancestral" Collection, while Map is not, after all, the operation of a pair of elements is still different from the operation of a single element, but if you carefully control the source code of Collection and Map And their direct pro-AbstractCollection and Abstractmap source code, you will find a lot of similar places, so we can still see MAP as the interface with blood relationships, and set, List, in parallel. With "no sequence set", "Order" and "Mapping", we can define a variety of abstract data structures, such as vector, linked list, stack, hash table, balance binary tree shown in Figure 1. Wait. But we need to remember, just Figure 2, placed in other members, check the API manual when you use it? However, general beginners are more likely to use some classes, like Vector, ArrayList, Hashmap, I have column here, showing common JCF members and their relationships:
Fathers Collections Framework: Collection set of unordered set new historical collections: Set ordered set: List Mapping: Dictionary map: Map AbstractSet SortedSet AbstractList AbstractSequentialList Hashtable AbstractMap SortedMap history collections new collection LinkedList WeakHashMap IdentityHashMap HashMap TreeMap HashSet TreeSet Vector ArrayList LinkedHashSet Stack Properties LinkedHashMap Maybe some concepts are not too understanding, such as what is "Historical Collection", HashTable, Hashmap, Triemap, how to achieve fast traversal, element finding or sorting, elements, nothing, We will study one by one below.
Details: The target and efficiency have the level of JCF, it is important to operate the specific operation of the object accommodated in the collection. When we learn the data structure, the teacher will always let you calculate the time complexity of an algorithm, maybe you This O (F (n)) is impatient, but in fact algorithm efficiency is an important factor.
1. Side focus: traversal vs. look
There are two main applications for the collection: I need to know which elements have a collection; find a specific element based on the conditions. The algorithm is often referred to as "traversal" and "lookup". Don't think that it is not used in our lives! For example, CCTV's "lucky 52", Li Wei let the entrant report a PDA's accurate price, what will he do? "2000" "High" "1000" "low" "1500" "low" ... until the answer is. There may be many people will choose this strategy, no matter whether he is a computer professional origin, don't know if he knows "data structure" and "folding", let alone say that he knows that there is still a price ratio O (log n) has a faster algorithm, but we often use this method naturally, this is not related to a person's industry, unless this person's RP is stronger, huh ... Exterior, traversal and modifications seem to be a pair of contradictions, one of the performance of data structures that can be inserted into delete elements is not optimal. The JCF then implements two customized data structures here according to the user's goals: hash tables (including Hashset and HashMap) and balanced binary trees (including TreeSet and TreeMap). Since the sorting is a unique requirement, sortedset and sortedmap are introduced, which are the sub-interfaces of AbstractSet and Abstractmap, respectively, and TreeSet and Treemap are their implementation. The person who is familiar with the data structure may be more understanding, the hash table is inserting, deleting, looking for such an operation is very fast, the time complexity is constant stage O (1); the balance binary tree is inserted, the deletion operation is more troublesome (need O (log n) price), but traversal and sorting are very fast. The choice is completely on the user's side focus, but because of the convenience of type conversion, we will only construct a collection with a hash table, and then convert it into a corresponding tree set to achieve better results.
Set set1 = new hashset (); set1.add (elem1); // By insertion element construct set set1.add (elem2); set1.add (elem3); set set2 = new treset (set); item all = set2. Iterator (); what (all.hasnext ()) {// Traversing set all.next (); ...} 2. History implementation vs. new implementation
The historical implementation is a term in JCF, and the accurate significance is not very clear, but it can be considered a prototype frame for JAVA 2 (JDK 1.2). After Java 2, JCF has begun to improve and strong, and some new classes have appeared in new classes for replacing members in the old versions, but because of various reasons, many classes represent the essence of traditional data structures. And some security reasons, so it is still useful.
Enumeration vs.
Iterator
Enumeration is a traditional collection traversal tool that is used in new JCFs that Iterator, iterator also has traversal features, and one contains one
Remove () method to delete the currently obtained element.
Dictionary vs.
Map
Dictionary is a class that has been marked as deprecated, implements the mapping function in the old version, and is now replaced by MAP. Their differences are: Dictionary is not KEY and VALUE can't be NULL, but Map allows empty keywords and values, which directly affects their progeny: HashTable and HashMap.
Vector vs.
ArrayList
Vector and arraylist are the embodiment of arrays in JCF, and remember the shortcomings of the array mentioned earlier? Vector and ArrayList are an array that can grow. Vector is a history, it and the main difference between ArrayList are that vector is a synchronization collection (or thread is safe), but ArrayList is not synchronized. Since synchronization requires a certain price, it is more than vector. Take more access efficiency. About synchronization We will also talk about it.
Hashtable vs.
Hashmap
Hashtable is a subclass of Dictionary, which belongs to historical implementation, and HashMap is a subclass of MAP, which is a new implementation. Their differences are different from the key and value described above, and have the same synchronization. HashTable is synchronized, but hashmap is not. But don't look down on it because HashTable is "old predecessors", it's a famous subclass.
Properties We are often used.
3. Synchronize vs. disagree
From the above description we seem to have such an impression: Historical implementation seems to be synchronized, but there is no new implementation. The reason for the need for synchronization is that there may be a plurality of threads to operate on the same collection: such as a thread is traversing a collection, but at the same time, another thread is inserted or deleted on the collection The traversal results of the first thread will be unpredictable, and for synchronization, it will throw one
ConcurrentModificationException, JCF becomes "fail-fast" in JCF. We can compare the source code of Vector and ArrayList, you can find that many methods of the vector are modified with the synchronized keyword, but ArrayList is not. 4. Tools that are easy to forget:
Collectes
with
Arrays
There are two classes in the right corner of Figure 1, there are two classes called collections (note, not collection!) And arrays, which is a powerful tool in JCF, but beginners tend to ignore. According to JCF documents, these two classes provide wrapper implementations, data structural algorithms, and array-related applications.
If you want everyone to forget the classic algorithm of "Folding ...", "Collection", "Sort", and the Collectes class offers a rich static method to help us to easily complete these annoying work in data structures:
BinarySearch: Folding half lookup.
SORT: Sort, here is a method similar to rapid sorting, and efficiency is still O (N * log n), but is a stable sorting method.
REVERSE: Operate the linear table, this is a classic examination question from the previous data structure!
Rotate: Take a linear table "rotate" with an element - wow, this function is too cool!
SWAP: Switch the position of two elements in a linear table.
......
Collectes have an important feature is "Wrapper", which provides some ways to convert a collection into a special collection:
Unmodifiablexxx: Convert to a read-only collection, here XXX represents six basic collection interfaces: Collection, List, Map, SET, SortedMap, and SortedSet. If you insert the read-only collection, you will thrown
UnsupportedOperationException exception.
Synchronizedxxx: Convert into synchronization set.
Singleton: Create a collection of only one element, here Singleton is generated, single element set,
SingletonList and
SingletonMap generates List and Maps of the units.
Empty set: Static attributes of Collectes
EMPTY_SET,
EMPTY_LIST and
EMPTY_MAP is represented.
In addition, we know that convert the collection into an object array to use collection
Toservation () method, we can easily convert an object array into a linear table (don't tell me you a place Add): arrays.
aslist ().
5. Wide
An important feature of the JCF we understand is that all objects in the collection will lose their own characteristics on the surface, and it is just an Object object, unless you put it forced type to convert it into them. Object. This is natural, a collection, an object's container, which is accommodated, not just a specific type of object. After J2SE 5.0, JCF began to introduce generic features. For example, we often encounter such applications, which are converted to a specific array, although Collection has toarray () methods, but unfortunately, all elements of this array All of the object type, our usual practice is to convert each element of the array with a FOR loop, although it is feasible, but it looks very awkward. If you have a generic, we can predecess it. Type, then TOARRAY can get the array we expect, all of the elements are all specified types. Oh, I don't know much about 5.0, and I can refer to J2SE 5.0 JCF documentation.
Small knot, I will take the horse's view of the JCF, and Java's veterans may be more annoying. The novices may be more like a high school mathematics class and university data structure, huh. This is just a small example, and it is very guiding for the application of basic knowledge to reality. Masters see mathematics, I think it is very beautiful and artistic, and the West has always distinguished mathematics from other natural sciences, and think it is closer to philosophy, like I am waiting for this whole day, I am still bothering to die. The customs still can't access it, Sigh ... Reference
IBM DeveloperWorks Tutorial: Java Collection Framework J2se Documentation: The Collections Framework The Java Tutorial JCF API
