Java数据结构与集合类.pdf

勿以恶小而为之，勿以善小而不为。刘备良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。汤显祖Java collections A collection allows a group of objects to be treated as a single unit.Arbitrary objects can be stored,retrieved and manipulated as elements of these collections.Collections Framework presents a set of standard utility classes to manage such collections.1.It contains core interfaces which allow collections to be manipulated independent of their implementations.These interfaces define the common functionality exhibited by collections and facilitate data exchange between collections.2.A small set of implementations that are concrete implementations of the core interfaces,providing data structures that a program can use.3.An assortment of algorithms to perform various operations such as,sorting and searching.Collections framework is interface based,collections are implemented according to their interface type,rather than by implementation types.By using the interfaces whenever collections of objects need to be handled,interoperability and interchangeability are achieved.By convention each of the collection implementation classes provide a constructor to create a collection based on the elements in the Collection object passed as argument.By the same token,Map implementations provide a constructor that accepts a Map argument.人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武丹青不知老将至，贫贱于我如浮云。杜甫This allows the implementation of a collection(Collection/Map)to be changed.But Collections and Maps are not interchangeable.Interfaces and their implementations in Java Collection|_ Set(no dupes,null allowed based on implementation)HashSet|_ SortedSet(Ordered Set)TreeSet|_ List(ordered collection,dupes OK)Vector,ArrayList,LinkedList Map(key-value pairs,null allowed based on implementation)HashTable,HashMap|_ SortedMap(Ordered Map)TreeMap Interface Description Collection A basic interface that defines the operations that all the classes that maintain collections of objects typically implement.Set Extends Collection,sets that maintain unique elements.Set interface is defined in terms of the equals operation SortedSet Extends Set,maintain the elements in a sorted order 万两黄金容易得，知心一个也难求。曹雪芹其身正，不令而行；其身不正，虽令不从。论语List Extends Collection,maintain elements in a sequential order,duplicates allowed.Map A basic interface that defines operations that classes that represent mappings of keys to values typically implement SortedMap Extends Map for maps that maintain their mappings in key order.Classes that implement the interfaces use different storage mechanisms.1.Arrays Indexed access is faster.Makes insertion,deletion and growing the store more difficult.2.Linked List Supports insertion,deletion and growing the store.But indexed access is slower.3.Tree Supports insertion,deletion and growing the store.Indexed access is slower.But searching is faster.4.Hashing Supports insertion,deletion and growing the store.Indexed access is slower.But searching is faster.However,requires the use of unique keys for storing data elements.Data Interfaces 勿以恶小而为之，勿以善小而不为。刘备人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武Structures Set SortedSet List Map SortedMap Hash Table HashSet HashMap HashTable Resizable Array ArrayList Vector Balanced Tree TreeSet TreeMap Linked List LinkedList Some of the operations in the collection interfaces are optional,meaning that the implementing class may choose not to provide a proper implementation of such an operation.In such a case,an UnsupportedOperationException is thrown when that operation is invoked.Interface Methods Description 海纳百川，有容乃大；壁立千仞，无欲则刚。林则徐宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明Collection Basic Operations int size();boolean isEmpty();boolean contains(Object element);boolean add(Object element);boolean remove(Object element);Used to query a collection about its contents,and add/remove elements.The add()and remove()methods return true if the collection was modified as a result of the operation.The contains()method checks for membership.Bulk Operations boolean containsAll(Collection c);boolean addAll(Collection c);boolean removeAll(Collection c);boolean retainAll(Collection c);void clear();Perform on a collection as a single unit.Operations are equivalent of set logic on arbitrary collections(not just sets).The addAll(),removeAll(),clear()and retainAll()methods are destructive.Array Operations Object toArray();Object toArray(Object a);These methods combined with()method provide the bridge between arrays and collections.穷则独善其身，达则兼善天下。孟子海纳百川，有容乃大；壁立千仞，无欲则刚。林则徐Iterators Iterator iterator();Iterator is an interface which has these methods.boolean hasNext();Object next();void remove();Returns an iterator,to iterate the collection.The remove()method is the only recommended way to remove elements from a collection during the iteration.Set No new methods defined.The add()method returns false,if the element is already in the Set.No exceptions are thrown.List Element Access by Index Object get(int index);Object set(int index,Object element);void add(int index,Object element);Object remove(int index);boolean addAll(int index,Collection c);First index is 0,last index is size()1.An illegal index throws IndexOutOfBoundsException.Element Search int indexOf(Object o);int lastIndexOf(Object o);If the element is not found,return 1.丈夫志四方，有事先悬弧，焉能钧三江，终年守菰蒲。顾炎武穷则独善其身，达则兼善天下。孟子List Iterators ListIterator listIterator();ListIterator listIterator(int index);ListIterator extends Iterator.It allows iteration in both directions.ListIterators additional methods:boolean hasPrevious();boolean previous();int nextIndex();int prviousIndex();void set(Object o);void add(Object o);Open Range View List subList(int fromIndex,int toIndex);Returns a range of the list from fromIndex(inclusive)to toIndex(exclusive).Changes to view are reflected in the list and vice versa.老当益壮，宁移白首之心；穷且益坚，不坠青云之志。唐王勃志不强者智不达，言不信者行不果。墨翟Map Basic Operations Object put(Object key,Object value);Object get(Object key);Object remove(Object key);boolean containsKey(Object key);boolean containsValue(Object value);int size();boolean isEmpty();The put method replaces the old value,if the map previously contained a mapping for that key.The get method returns null,if the specified key couldnt be found in the map.Bulk Operations void putAll(Map t);void clear();putAll()adds all the elements from the specified map.clear()removes all the elements from the map.先天下之忧而忧，后天下之乐而乐。范仲淹常将有日思无日，莫待无时思有时。增广贤文Collection Views Set keySet();Collection values();Set entrySet();Note that the values()method,returns a Collection,not a set.Reason is,multiple unique keys can map to the same value.Provide different views on a Map.Changes to views are reflected in the map and vice versa.Each pair is represented by an Object implementing interface.Object getKey();Object getValue();Object setValue(Object value);SortedSet Range View Operations SortedSet headSet(Object toElement);SortedSet tailSet(Object fromElement);SortedSet subSet(Object fromElement,Object toElement);fromElement is inclusive,toElement is exclusive.The views present the elements sorted in the same order as the underlying sorted set.Min-Max Points Object first();Object last();Return the first(lowest)and last(highest)elements.Comparator Access Comparator comparator();Returns the compartor associated with this SortedSet,or null if it uses natural ordering.人不知而不愠，不亦君子乎？论语忍一句，息一怒，饶一着，退一步。增广贤文SortedMap Range View Operations SortedMap headMap(Object toKey);SortedSet tailMap(Object fromKey);SortedSet subMap(Object fromKey,Object toKey);SortedMap is sorted with keys.fromKey is inclusive,toKey is exclusive.The views present the elements sorted in the same order as the underlying sorted map.Min-Max Points Object firstKey();Object lastKey();Return the first(lowest)and last(highest)keys.Comparator Access Comparator comparator();Returns the compartor associated with this SortedMap,or null if it uses natural ordering.Sorting in SortedSets and SortedMaps can be implemented in two ways.1.Objects can specify their natural order by implementing Comparable interface.Many if the standard classes in Java API,such as wrapper classes,String,Date and File implement this interface.This interface defines a single method:int compareTo(Object o)returns negative,zero,positive if the current object is less than,equal to or greater than the specified object.In this case a natural comparator queries objects implementing Comparable about their natural order.Objects implementing this interface can be used:As elements in a sorted set.丹青不知老将至，贫贱于我如浮云。杜甫良辰美景奈何天，便赏心乐事谁家院。则为你如花美眷，似水流年。汤显祖 As keys in sorted map.In lists which can be sorted automatically by the()method.2.Objects can be sorted by specific comparators,which implement Comparator interface.This interface defines the following method:int compare(Object o1,Object o2)returns negative,zero,positive if the first object is less than,equal to or greater than the second object.It is recommended that its implementation doesnt contradict the semantics of the equals()method.Specific Comparators can be specified in the constructors of SortedSets and SortedMaps.All classes provide a constructor to create an empty collection(corresponding to the class).HashSet,HashMap,HashTable can also be specified with an initial capacity as well as a load factor(the ratio of number of elements stored to its current capacity).Most of the time,default values provide acceptable performance.A Vector,like an array,contains items that can be accessed using an integer index.However,the size of a Vector can grow and shrink as needed to accommodate adding and removing items after the Vector has been created.Vector(5,10)means initial capacity 5,additional allocation(capacity increment)by 10.丈夫志四方，有事先悬弧，焉能钧三江，终年守菰蒲。顾炎武忍一句，息一怒，饶一着，退一步。增广贤文 Stack extends Vector and implements a LIFO stack.With the usual push()and pop()methods,there is a peek()method to look at the object at the top of the stack without removing it from the stack.Dictionary is an obsolete class.HashTable extends dictionary.Elements are stored as key-value pairs.Vector and HashTable are the only classes that are thread-safe.ArrayList(does what Vector does),HashMap(does what HashTable does),LinkedList and TreeMap are new classes in Java In Java,Iterator duplicates the functionality of Enumeration.New implementations should consider Iterator.Collections is a class,Collection is an interface.Collections class consists exclusively of static methods that operate on or return collections.Sorting and Searching algorithms in the Collections class.static int binarySearch(List list,Object key)static void fill(List list,Object o)static void shuffle(List list,Object o)static void sort(List list)Factory methods to provide thread-safety and data immutability.These methods return synchronized(thread-safe)/immutable collections from the specified collections.List safeList=(new LinkedList();SortedMap fixedMap=(new SortedMap();Constants to denote immutable empty collections in the Collections class:天行健，君子以自强不息。地势坤，君子以厚德载物。易经非淡泊无以明志，非宁静无以致远。诸葛亮EMPTY_SET,EMPTY_LIST and EMPTY_MAP.Collections class also has the following methods:Method Description public static Set singleton(Object o)Returns an immutable set containing only the specified object public static List singletonList(Object o)Returns an immutable list containing only the specified object public static Map singletonMap(Object key,Object value)Returns an immutable map containing only the specified key,value pair.public static List nCopies(int n,Object o)Returns an immutable list consisting of n copies of the specified object.The newly allocated data object is tiny(it contains a single reference to the data object).This method is useful in combination with the method to grow lists.The class Arrays,provides useful algorithms that operate on arrays.It also provides the static asList()method,which can be used to create List views of arrays.Changes to the List view affects the array and vice versa.The List size is the array size and cannot be 穷则独善其身，达则兼善天下。孟子丈夫志四方，有事先悬弧，焉能钧三江，终年守菰蒲。顾炎武modified.The asList()method in the Arrays class and the toArray()method in the Collection interface provide the bridge between arrays and collections.Set mySet=new HashSet(myArray);String strArray=(String)();All concrete implementations of the interfaces in package are inherited from abstract implementations of the interfaces.For example,HashSet extends AbstractSet,which extends AbstractCollection.LinkedList extends AbstractList,which extends AbstractCollection.These abstract implementations already provide most of the heavy machinery by implementing relevant interfaces,so that customized implementations of collections can be easily implemented using them.BitSet class implements a vector of bits that grows as needed.Each component of the bit set has a boolean value.The bits of a BitSet are indexed by nonnegative integers.Individual indexed bits can be examined,set,or cleared.One BitSet may be used to modify the contents of another BitSet through logical AND,logical inclusive OR,and logical exclusive OR operations.By default,all bits in the set initially have the value false.A BitSet has a size of 64,when created without specifying any size.ConcurrentModificationException exception(extends RuntimeException)may be thrown by methods that have detected concurrent modification of a backing object when such modification is not permissible.谋事在人，成事在天！增广贤文忍一句，息一怒，饶一着，退一步。增广贤文For example,it is not permssible for one thread to modify a Collection while another thread is iterating over it.In general,the results of the iteration are undefined under these circumstances.Some Iterator implementations(including those of all the collection implementations provided by the JDK)may choose to throw this exception if this behavior is detected.Iterators that do this are known as fail-fast iterators,as they fail quickly and cleanly,rather that risking arbitrary,non-deterministic behavior at an undetermined time in the future.The big advantage of the collections over arrays is that the collections are growable,you do not have to assign the size at creation time.The drawback of collections is that they only store objects and not primitives and this comes with an inevitable performance overhead.Arrays do not directly support sorting,but this can be overcome by using the static methods of the Collections.Here is an example.import.*;public class Sort public static void main(String argv)Sort s=new Sort();Sort()String s=new String4;s0=z;s1=b;s2=c;s3=a;勿以恶小而为之，勿以善小而不为。刘备人不知而不愠，不亦君子乎？论语 (s);for(int i=0;i;i+)The following example illustrates how you can add objects of different classes to a Vector.This contrasts with arrays where every element must be of the same type.The code then walks through each object printing to the standard output.This implicitly access the toString()method of each object.import.*;import.*;public class Vec public static void main(String argv)Vec v=new Vec();();/End of main public void amethod()Vector mv=new Vector();/Note how a vector can store objects /of d