Collections API

صفحه 1:
Collections API Alex Miller, Terracotta 

صفحه 2:
Topics Data structures Axes of comparison Collection interfaces Collection implementations Algorithms Concurrency 

صفحه 3:
History JDK 1.0:Vector, Dictionary, Hashtable, Stack, Enumeration JDK 1.2: Collection, Iterator, List, Set, Map, ArrayList, HashSet, TreeSet, HashMap, WeakHashMap JDK 1.4:RandomAccess, IdentityHashMap, LinkedHashMap, LinkedHashSet JDK 1.5: Queue, java.util.concurrent, ... JDK 1.6: Deque, ConcurrentSkipListSet/Map, ... JDK 1|.7:TransferQueue, LinkedTransferQueue 

صفحه 4:
Collection Interfaces <<interface>> lterable <<interface>> Collection 1 | 15 l<<interface>> <<interface>> <<interface>> Set List Queue ۱ f I<<interface>> 16 eae 15 ae <<interface>> <<interface>> Deque BlockingQueue 1 1 16 Issinterface>> 16 NavigableSet <<interface>> BlockingDeque 

صفحه 5:
Map Interfaces <<interface>> SortedMap java.util. concurrent ۸ 15 6 <<interface>> <<interface>> ConcurrentMap NavigableMap 1 16 <sinterface>> ConcurrentNavigableMap 

صفحه 6:
Comparing Implementations Operation performance Concurrency Iterator style Data types Sorting and ordering Null support 

صفحه 7:
Collection Interface <<interface>> Iterable<T> iterator() : Iterator<T> ۸ ssinterface>> Collection<E> add(E e) : boolean addAll(Collection<? extends E> c) : boolean contains(Object 0) : boolean containsAll(Collection<?> c) : boolean isEmpty() : boolean size() : int remove(Object 0) : boolean clear() removeAll(Collection<?> c) : boolean retainAll(Collection<?> c) : boolean toArray() : Object(] toArray(T[] a) : 0 

صفحه 8:
List Interface <sinterface>> ListsE> add(int index, E element) addAll(int index, Collection<? extends E> c) : boolean get(int index) : E remove(int index) : E set(int index, E element) : E indexOf(Object o) : int lastindexOf(Object 0) : int subList(int fromindex, int tolndex) : List<E> listlterator() : Listlterator<E> listiterator(int index) : Listlterator<E> 

صفحه 9:
List Implementations \<<interface>> ist Java.utilconcurrent ۱ 1 15 ArrayList LinkedList ICopyOnWriteArrayList’ 

صفحه 10:
Data Structure: Array © Indexed access e Uses offset from memory address for fast memory access ©» In Java - fixed size memory block with VM- level support 

صفحه 11:
Data structure: Linked List ©» Dynamic structure made of pointers ©» Easy to insert and delete new elements ® No indexed access 

صفحه 12:
List Comparison Data 7 Structure Sorting Iterator Nulls? Array Fail-fast Linked Lie Linked list Fail-fast CopyOnWrite ArrayList Array Snapshot 

صفحه 13:
Computational Complexity all / ‏بر‎ 

صفحه 14:
List Performance Comparison ۳ ۳ [remo | ‏ع‎ orn LinkedList 0)۱( O(n) O(n) leet O(n) | ©0( | Of) 

صفحه 15:
Iterators ©» Fail-fast - work on live data, but become invalid when live data is modified » Weakly consistent - work on live data, safe, reflect updates and deletes, but not inserts @ Snapshot - work ona snapshot of the live data, fast, safe, but possibly stale Demo 

صفحه 16:
Set Interfaces |s<interface>> Set 1 \<<interface>> SortedSet 1 1.0 \<<interface>> INavigableSet 

صفحه 17:
SortedSet first() :E 2560 ۴ headSet(E toElem) : SortedSet<E> subSet(E fromElem, E toElem) : SortedSet<E> tailSet(E fromElem) : SortedSet<E> comparator() : Comparator<? super E> 

صفحه 18:
NavigableSet pollFirst() : E pollLast() : subSet(E from, boolean inclusive, E to, boolean inclusive) : NavigableSet<E> headSet(E to, boolean inclusive) : NavigableSet<E> tailSet(E from, boolean inclusive) : NavigableSet<E> ceiling(E e) :E floor(E e):E higher(E e) :E lower(E e) ۴ descendingSet() : NavigableSet<E> descendinglterator() : Iterator<E> 

صفحه 19:
Set Implementations k<interface>> SortedSet 16 >>۱0۱6۲۲206<< INavigableSet 

صفحه 20:
Comparing Sets Data Iterator Nulls? Structure HashSet Hash table Fail-fast Linked Hash table + HashSet linked |i Red-black tree CopyOnWrite Concurrent 

صفحه 21:
Skip Lists دا سد سد سد دا محر @ Series of linked lists @ Reasonably fast search, add, remove @ Lock-free implementation! 

صفحه 22:
Comparing Set Performance add contains next HashSet 0)۱( 0۵)۱( Olh/n) Linked HashSet CopyOnWrite Concurrent Demo 

صفحه 23:
Queues and Deques 15 <<interface>> Queue 1 16 <<interface>> Deque 4 15 16 <<interface>> <<interface>> BlockingQueue BlockingDeque 

صفحه 24:
Queue Methods Throws Returns special exception value Remove remove() poll() Examine element() peek() 

صفحه 25:
BlockingQueue Methods -_ 2-2 ocks exception special out poll(time, Remove | remove() | _poll() take() unit) Examine | element()| peek() x 

صفحه 26:
ueue Implementations Jove uth. coneurent 17. <interface>> | TransferQueus 0 I 17 LinkedTransferQueue Demo 15 <<interface>> Queue: $8 PriorityQueue) i 15 15 ‘Concurrent <<intetface>> | LinkedQueue BiockingQueue 1 1 ] ‏مد | مه‎ ‘Array Linked BlockingQuoso BlckingQuouo 

صفحه 27:
Data Structure: Priority Heap tT 2 ws , @ Balanced binary tree © Root is always highest priority @ Inserts and removes cause re-balancing 

صفحه 28:
Deque Methods Tail: ۳ Tail: Throws Special value exception offerLast(e) addLast(e) Queue: offer Queue: add removeLast() pollLast() getLast() peekLast() Head: Special value offerFirst(e) pollFirst() Queue: poll peekFirst() Queue: peek Stack peek Head: Throws exception addFirst(e) Insert Stack: push removeFirst() Queue: remove Stack pop getFirst() Examine Queue: element 

صفحه 29:
Blocking Deque Methods 0 HEAD: Throws exception Spec Blocks Times out value Insert addFirst(e) addLast(e) offerlast(e) putLast(e) offerLast(e,time,u Insert Queue: add Queue: offer Queue: put Queue: offer Remove removelast() pollLast() takeLast() pollLast(time, unit) Examine getLast() peekLast() x x 

صفحه 30:
Deque Implementations 16 java.util concurrent LinkedList ArrayDeque 16 ssinterfaces> Deque 16 <<interface>> BlockingDeque i 16 LinkedBlockingDeque 

صفحه 31:
Comparing Queue Implementations Das Swucare na Priory ‏مسج‎ Priory hep Ne ‏عد نا‎ ms ‏اهنا‎ ee ‏ا الا‎ ‎Neo‏ ام | ‎FRO‏ ال ا ‎No‏ ال الا | ‎ary‏ مب قرم ‎PriorityBlockingQueue Priority heap Sorted Unbounded No SynchronousQueue none! N/A 0 ‏ول‎ ‎DelayQueue Priority heap Delayed order | Unbounded No ‎LinkedBlockingQueue Linked list FIFO (Un)bounded No ‎LinkedBlockingDeque Linked list FIFO (Un)bounded No ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 32:
Queue Performance offer peek poll size Unked it ou ArrayDeque 600 60 6) 6) AraylochineQuese 60 ProrBlockingQueue 50 Synctronous Quen on ‏عمو وه‎ oun ‏موم مهس‎ 50 ‏جوم همست‎ 50 

صفحه 33:
TransferQueue Producers wait for consumers to receive elements. Useful for message passing. Similar to a broader version of SynchronousQueue. hasWaitingConsumer() : boolean getWaitingConsumerCount() : int transfer(E e) tryTransfer(E e) : boolean tryTransfer(E e, long timeout, TimeUnit unit) : boolean 

صفحه 34:
Map Interfaces <<interface>> SortedMap java.util. concurrent ۸ 15 6 <<interface>> <<interface>> ConcurrentMap NavigableMap 1 16 <sinterface>> ConcurrentNavigableMap 

صفحه 35:
Map put(E key,V value) :V putAll(Map<? extends K, ? extends V> m) remove(Object key) :V clear() containsKey(Object key) : boolean containsValue(Object value) : boolean isEmpty() : boolean size() : int get(Object key) :V entrySet() : Set<Map.Entry<K,V>> keySet() : Set<K> values() : Collection<V> 

صفحه 36:
SortedMap firstKey() :K lastKey() :K headMap(K to) : SortedMap<K,V> subMap(K from, K to) : SortedMap<K,V> tailMap(K from) : SortedMap<K,V> comparator() : Comparator<? super K> 

صفحه 37:
NavigableMap firstEntry() : Map-Entry<K,V> lastEnery() : Map.Entry<K,V> ceilingEntry(K key) : Map.Entry<K,V> ceilingKey(K key) :K floorEntry(K key) : MapEntry<K,V> floorKey(K key) :K higherEntry(K key) : Map.Entry<K,V> higherKey(K key) :K lowerEntry() : MapEntry<K,V> lowerEntry(K key) : K navigableKeySet() : NavigableSet<K> pollFirstEntry() : Map.Entry<K,V> pollLastEncry() : Map.Entry<K.V> headMap(K to, boolean inclusive) : NavigableMap<K,V> subMap(K from, boolean frominc, K to, boolean tolnc) : NavigableMap<K,V> tailMap(K from, boolean inclusive) : NavigableMap<K,V> descendingKeySet() : NavigableSet<K> descendingMap() : NavigableMap<K,V> 

صفحه 38:
ConcurrentMap putlfAbsent(K key,V value) :V remove(Object key, Object value) : boolean replace(K key, V value) :V replace(K key,V oldValue,V newValue) : boolean 

صفحه 39:
Map Implementations <<interface>>| Map jJavautilconcurrert 48 <<interface>> <<interface>> SortedMap ConcurrentMep 1 16 <<interface>> NavigableMap 16 

صفحه 40:
Comparing Map Implementations WeakHashMap EnumMap TreeMap 

صفحه 41:
Map Performance ال »۳ [ ۰ 1 ۳ ا ...و HashMap LinkedHashMap EnumMap (1) 00 TreeMap O(log n) O(log n) ConcurrentHashMap OU!) 000 ‏واه‎ Demo 

صفحه 42:
Collections Factories: Wrappers: - EMPTY_SET + unmodifiableCollection - ۶۲۴۲۷ ۲ + unmodifiableSet - ۶۲۱۳۲۷ ۸۵۲ - unmodifiableSortedSet - emptySet - unmodifiableList - emptyList - unmodifiableMap - emptyMap - unmodifiableSortedMap - singleton - synchronizedCollection - singletonList - synchronizedSet - singletonMap - synchronizedSortedSet ~ nCopies - synchronizedList - list(Enumeration) - synchronizedMap - synchronizedSortedMap Comparators: - checkedCollection - reverseOrder - checkedSet - checkedSortedSet Miscellaneous: - checkedList - addAll - checkedMap = enumeration - checkedSortedMap Collection algorithms: -min -max - frequency + disjoint List algorithms: + sort - binarySearch - reverse - shuffle + swap - fill + copy - replaceAll + indexOfSubList + lastIndexOfSubList 

صفحه 43:
References Concurrency JSR 166 Interest Site, http://gee.cs.oswego.edu/dl/concurrency- interest/index.html Introduction to Algorithms, Cormen et al lava Concurrency in Practice, Goetz et al lava Generics and Collections, Naftalin and Wadler Java Platform API Specification, http://java.sun.com/javase/6/docs/api/ Lecture on Skip Lists, Prof. Charles Leiserson, http://ocw.mit.edu/ ans7870/6/6.046j/f05/lecturenotes/ocw-6.046-260ct2005.mp3 

صفحه 44:
Bonus Slides 

صفحه 45:
Other Collection Libraries Google Collections Apache Commons Collections High-Scale Library (Cliff Click) Gnu Trove Doug Lea’s Collections 

صفحه 46:
Google Collections @ http://code.google.com/p/google-collections/ e New types: © BiMap - bidirectional map ‎Multiset - set that allows dups‏ وه ‎© Multimap - like Map, but allows dup keys » New implementations ‎@ ReferenceMap - concurrent, references ‎ ‎ ‎ 

صفحه 47:
Google Collections e@ Utilities: Comparators - primitives, compound, function-based, etc Iterators - cycle, skip, find, transform, concat Helpers for standard Collection types, primitive arrays, etc And much more... 

صفحه 48:
Apache Commons Collections http://commons.apache.org/collections/ New types: ٠ Bags © Buffer ٠ BidiMap Decorators: type checking, transformation Implementations: composites, identity map, reference map Comparators, iterators, adapters, etc 

صفحه 49:
High-scale Lib @ http://sourceforge.net/projects/high-scale- lib e Designed for non-blocking use in large core environments @ Non-blocking hash table, set ‏وه‎ From Cliff Click at Azul 

صفحه 50:
Gnu Trove @ http://trove4j.sourceforge.net/ e@ High-performance Map implementations © Customizable hash strategies © Primitive-specific ©» Stack, List, Set, etc © Primitive-specific @ Procedure-based iteration 

صفحه 51:
Doug Lea’s Collections @ http://gee.cs.oswego.edu/dl/classes/ collections/index.html @ No longer supported