Java Collections Overview

Java Collections Overview思维导图，包括：References、Collection、List、Set、Wrappers、Collections Static Methods、Queue、Map。

Java Collections Overview

• References
  • Java Platform Standard Edition 7 Documentation
  • Java How to Program，9th Edition 2012，Chapter 20，Generic Collections
  • http://www.jroller.com/VelkaVrana/entry/java_1_6_collections_class
• Collection
  • Decription
    • The root interface in the collection hierarchy
    • represents a group of objects
    • methods may, but are not required to, throw an UnsupportedOperationException if the invocation would have no effect on the collection
  • Constructor
    • a void (no arguments) constructor
    • a constructor with a single argument of type Collection
  • api
    • boolean add(E e)
      • optional
    • boolean addAll(Collection<? extends E> c)
      • Appends all of the elements in the specified collection to the end of this list
      • in the order that they are returned by the specified collection's iterator
      • optional
    • void clear()
      • optional
    • boolean contains(Object o)
    • boolean containsAll(Collection<?> c)
    • boolean isEmpty()
    • Iterator<E> iterator()
    • boolean remove(Object o)
      • optional
    • boolean removeAll(Collection<?> c)
      • optional
    • boolean retainAll(Collection<?> c)
      • Retains only the elements in this collection that are contained in the specified collection
      • optional
    • int size()
    • Object[] toArray()
    • <T> T[] toArray(T[] a)
• List
  • definition
    • a finite ordered collection of values
    • the same value may occur more than once
    • a basic example of containers
    • a computer representation of the mathematical concept of a finite sequence
  • class diagram
  • api
    • int indexOf(Object o)
    • int lastIndexOf(Object o)
    • ListIterator<E> listIterator()
    • ListIterator<E> listIterator(int index)
    • E get(int index)
    • E remove(int index)
    • E set(int index, E element)
    • List<E> subList(int fromIndex, int toIndex)
  • implementation
    • ArrayList
    • LinkedList
      • api
        • void addFirst(E e)
        • void addLast(E e)
        • Iterator<E> descendingIterator()
        • E element()
          • Retrieves, but does not remove, the head (first element) of this list
        • E getFirst()
        • E getLast()
        • boolean offer(E e)
          • Adds the specified element as the tail (last element) of this list
        • boolean offerFirst(E e)
          • Inserts the specified element at the front of this list
        • boolean offerLast(E e)
          • Inserts the specified element at the end of this list
        • E peek()
          • Retrieves, but does not remove, the head (first element) of this list
        • E peekFirst()
        • E peekLast()
        • E poll()
          • Retrieves and removes the head (first element) of this list
        • E pollFirst()
        • E pollLast()
        • E pop()
        • void push(E e)
        • E removeFirst()
        • boolean removeFirstOccurrence(Object o)
        • E removeLast()
        • boolean removeLastOccurrence(Object o)
• Set
  • definition
    • contains no duplicate elements
    • at most one null element
    • models the mathematical set abstraction
  • class diagram
  • api
    • boolean add(E e)
      • optional
    • boolean addAll(Collection<? extends E> c)
      • Appends all of the elements in the specified collection to the end of this list
      • in the order that they are returned by the specified collection's iterator
      • optional
    • void clear()
      • optional
    • boolean contains(Object o)
    • boolean containsAll(Collection<?> c)
    • boolean isEmpty()
    • Iterator<E> iterator()
    • boolean remove(Object o)
      • optional
    • boolean removeAll(Collection<?> c)
      • optional
    • boolean retainAll(Collection<?> c)
      • Retains only the elements in this collection that are contained in the specified collection
      • optional
    • int size()
    • Object[] toArray()
    • <T> T[] toArray(T[] a)
  • implementation
    • HashSet
      • Constructor
        • HashSet()
        • HashSet(Collection<? extends E> c)
        • HashSet(int initialCapacity)
        • HashSet(int initialCapacity, float loadFactor)
      • Description
        • offers constant time performance for the basic operations (add, remove, contains and size)
        • makes no guarantees as to the iteration order of the set
    • LinkedHashSet
      • Constructor
        • LinkedHashSet()
        • LinkedHashSet(Collection<? extends E> c)
        • LinkedHashSet(int initialCapacity)
        • LinkedHashSet(int initialCapacity, float loadFactor)
      • Description
        • it maintains a doubly-linked list running through all of its entries
        • keeps the order in which elements were inserted into the set (insertion-order)
        • insertion order is not affected if an element is re-inserted into the set
    • TreeSet
      • Description
        • based on a TreeMap
        • provides guaranteed log(n) time cost for the basic operations (add, remove and contains)
        • ordered using natural ordering, or by a Comparator provided at set creation time
      • Constructor
        • TreeSet()
        • TreeSet(Collection<? extends E> c)
        • TreeSet(Comparator<? super E> comparator)
        • TreeSet(SortedSet<E> s)
      • api
        • E ceiling(E e)
        • E higher(E e)
        • E floor(E e)
        • E lower(E e)
        • Comparator<? super E> comparator()
        • Iterator<E> descendingIterator()
        • NavigableSet<E> descendingSet()
        • E first()
        • E last()
        • E pollFirst()
        • E pollLast()
        • SortedSet<E> headSet(E toElement)
          • Returns a view of the portion of this set whose elements are strictly less than toElement.
        • NavigableSet<E> headSet(E toElement, boolean inclusive)
        • SortedSet<E> tailSet(E fromElement)
          • Returns a view of the portion of this set whose elements are greater than or equal to fromElement
        • NavigableSet<E> tailSet(E fromElement, boolean inclusive)
        • NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
        • SortedSet<E> subSet(E fromElement, E toElement)
          • Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
• Wrappers
  • synchronized
    • Description
      • synchronization wrappers are used for collections that might be accessed by multiple threads
    • api
      • Collection< T > synchronizedCollection( Collection< T > c )
      • List< T > synchronizedList( List< T > aList )
      • Set< T > synchronizedSet( Set< T > s )
      • SortedSet< T > synchronizedSortedSet( SortedSet< T > s )
      • Map< K, V > synchronizedMap( Map< K, V > m )
      • SortedMap< K, V > synchronizedSortedMap( SortedMap< K, V > m )
  • Unmodifiable
    • Description
      • throw UnsupportedOperationExceptions if attempts are made to modify the collection
      • use an unmodifiable wrapper to create a collection that offers read-only access to others, while allowing read/write access to yourself
    • api
      • Collection< T > unmodifiableCollection( Collection< T > c )
      • List< T > unmodifiableList( List< T > aList )
      • Set< T > unmodifiableSet( Set< T > s )
      • SortedSet< T > unmodifiableSortedSet( SortedSet< T > s )
      • Map< K, V > unmodifiableMap( Map< K, V > m )
      • SortedMap< K, V > unmodifiableSortedMap( SortedMap< K, V > m )
• Collections Static Methods
  • sort
    • static <T extends Comparable<? super T>> void sort(List<T> list)
    • static <T> void sort(List<T> list, Comparator<? super T> c)
  • binarySearch
    • static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
    • static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
  • reverse
    • static void reverse(List<?> list)
  • shuffle
    • static void shuffle(List<?> list)
    • static void shuffle(List<?> list, Random rnd)
  • fill
    • static <T> void fill(List<? super T> list, T obj)
  • copy
    • static <T> void copy(List<? super T> dest, List<? extends T> src)
  • min
    • static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
    • static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
  • max
    • static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
    • static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
  • addAll
    • static <T> boolean addAll(Collection<? super T> c, T... elements)
      • Adds all of the specified elements to the specified collection
  • frequency
    • static int frequency(Collection<?> c, Object o)
      • Calculates how many collection elements are equal to the specified element
  • disjoint
    • static boolean disjoint(Collection<?> c1, Collection<?> c2)
      • Determines whether two collections have no elements in common
• Queue
  • class diagram
• Map
  • definition
    • maps keys to values
      • A map cannot contain duplicate keys
      • each key can map to at most one value
    • collection views
      • a set of keys
      • collection of values
      • set of key-value mappings
  • class diagram
  • api
    • void clear()
    • boolean containsKey(Object key)
    • boolean containsValue(Object value)
    • Set<Map.Entry<K,V>> entrySet()
      • returns a collection-view of the map
      • The only way to obtain a reference to a map entry is from the iterator of this collection-view
      • valid only for the duration of the iteration
    • V get(Object key)
    • Set<K> keySet()
    • V put(K key, V value)
    • void putAll(Map<? extends K,? extends V> m)
    • V remove(Object key)
    • Collection<V> values()
  • implementation
    • HashMap
      • Description
        • roughly equivalent to Hashtable
        • permits null values and the null key
        • unsynchronized
        • makes no guarantees as to the order of the map
        • constant-time performance for the basic operations
      • Constructor
        • HashMap()
          • Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75)
        • HashMap(int initialCapacity)
        • HashMap(int initialCapacity, float loadFactor)
        • HashMap(Map<? extends K,? extends V> m)
    • LinkedHashMap
      • Description
        • maintains a doubly-linked list running through all of its entries
        • insertion-order
        • constant-time performance for the basic operations
        • the added expense of maintaining the linked list
        • Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity
      • Constructor
        • LinkedHashMap()
        • LinkedHashMap(int initialCapacity)
        • LinkedHashMap(int initialCapacity, float loadFactor)
        • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
        • LinkedHashMap(Map<? extends K,? extends V> m)
      • api
        • protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
    • TreeMap
      • Description
        • A Red-Black tree based NavigableMap implementation
        • sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time
        • provides guaranteed log(n) time cost for the containsKey, get, put and remove operations
      • Constructor
        • TreeMap()
        • TreeMap(Comparator<? super K> comparator)
        • TreeMap(Map<? extends K,? extends V> m)
        • TreeMap(SortedMap<K,? extends V> m)
      • api
        • Map.Entry<K,V> ceilingEntry(K key)
          • a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key
        • K ceilingKey(K key)
        • Map.Entry<K,V> floorEntry(K key)
        • K floorKey(K key)
        • NavigableSet<K> descendingKeySet()
        • NavigableMap<K,V> descendingMap()
        • Map.Entry<K,V> firstEntry()
        • K firstKey()
        • Map.Entry<K,V> lastEntry()
        • K lastKey()
        • SortedMap<K,V> headMap(K toKey)
        • NavigableMap<K,V> headMap(K toKey, boolean inclusive)
        • SortedMap<K,V> tailMap(K fromKey)
        • NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
        • Map.Entry<K,V> higherEntry(K key)
        • K higherKey(K key)
        • Map.Entry<K,V> lowerEntry(K key)
        • K lowerKey(K key)
        • NavigableSet<K> navigableKeySet()
        • Map.Entry<K,V> pollFirstEntry()
        • Map.Entry<K,V> pollLastEntry()
        • NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
        • SortedMap<K,V> subMap(K fromKey, K toKey)