Java 2 Collections
Framework
Leonardo Cole Neto
Roteiro
Introdução
 Interfaces
 Implementações
 Algoritmos
 Customizando Implementações
 Resolvendo Problemas Comuns

Introdução

O que é uma coleção?
 Um
objeto que agrupa múltiplos elementos
em uma única unidade
Usadas para armazenar, recuperar e
manipular elementos que formam um
grupo natural.
 Ex.: Vector, Hashtable, array (JDK 1.1)

Collections Framework


Conjunto de interfaces, implementações e
algoritmos
Vantagens
 Reduz
esforço de programação
 Aumenta velocidade e qualidade na programação
 Permite interoperabilidade entre API´s
 Reduz esforço para aprender uma nova API
 Reduz esforço para criar uma nova API
 Promove reuso
Interfaces
Interfaces

São utilizadas sempre que possível
 Parâmetros
de métodos
 Retorno dos métodos
Permite polimorfismo
 Existem operações opcionais

 UnsupportedOperationException
Collection



Raiz da hierarquia
Grupo mais genérico de elementos
Não garante nas implementações
 Duplicatas
 Ordenação


Não possui nenhuma implementação direta
Iterator, extrutura de navegação
 next,
hasNext, remove(optional)
Collection
public interface Collection {
// Basic Operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(Object element);
// Optional
boolean remove(Object element); // Optional
Iterator iterator();
// Bulk Operations
boolean containsAll(Collection c);
boolean addAll(Collection c);
//
boolean removeAll(Collection c); //
boolean retainAll(Collection c); //
void clear();
//
// Array Operations
Object[] toArray();
Object[] toArray(Object a[]);
}
Optional
Optional
Optional
Optional
Set






Extends Collection
Não contém duplicatas
Não garante ordem entre os elementos
Não acrescenta métodos
Caracterização de tipo
Operações




Subconjunto (containsAll)
União (addAll)
Intercessão (reatinaAll)
Diferença (removeAll)
List






Extends Collection
Coleção ordenada (Sequência)
Pode ter duplicatas
Controle na posição de inserção ou remoção
Acesso aos elementos pelo índice
ListIterator
 hasPrevious,previous,
nextIndex, previousIndex
List
public interface List extends Collection {
// Positional Access
Object get(int index);
Object set(int index, Object element);
void add(int index, Object element);
Object remove(int index);
abstract boolean addAll(int index, Collection c);
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator listIterator();
ListIterator listIterator(int index);
// Range-view
List subList(int from, int to);
}
//
//
//
//
Optional
Optional
Optional
Optional
Map
Mapeamento de chaves em valores
 Não possui chaves duplicadas
 Cada chave leva a somente um elemento
 Para uma busca efetiva, o objeto da chave
deve reimplementar os métodos:

 hashCode
 equals
Map
public interface 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();
// Bulk Operations
void putAll(Map t);
void clear();
// Collection Views
public Set keySet();
public Collection values();
public Set entrySet();
// Interface for entrySet elements
public interface Entry {
Object getKey();
Object getValue();
Object setValue(Object value);
}
}
Ordenação de Objetos

java.lang.Comparable
 Ordem natural
 compareTo(object)

java.util.Comparator
 Provê multiplas formas
 compare(object,object)

Retornos
 Inteiro negativo
 Zero = iguais
 Inteiro

de ordenação
= menor que
positivo = maior que
Não são elementos do framework, apenas
estruturas complementares
Ordenação de Objetos
Class
Natural Ordering
Byte
signed numerical
Character
unsigned numerical
Long
signed numerical
Integer
signed numerical
Short
signed numerical
Double
signed numerical
Float
signed numerical
BigInteger
signed numerical
BigDecimal
signed numerical
File
system-dependent lexicographic on pathname.
String
lexicographic
Date
chronological
CollationKey
locale-specific lexicographic
SortedSet
Extends Set
 Elementos ordenados de forma ascendente
 Algumas operações a mais para aproveitar a vantagem da ordenação
public interface SortedSet extends Set {
// Range-view
SortedSet subSet(Object fromElement, Object
toElement);
SortedSet headSet(Object toElement);
SortedSet tailSet(Object fromElement);

// Endpoints
Object first();
Object last();
// Comparator access
Comparator comparator();
}
SortedMap
Extends Map
 Mapeamento onde as chaves são ordenadas de forma ascendente.
public interface SortedMap extends Map {
Comparator comparator();

SortedMap subMap(Object fromKey, Object toKey);
SortedMap headMap(Object toKey);
SortedMap tailMap(Object fromKey);
Object firstKey();
Object lastKey();
}
Implementações
Implementations
Hash Table Resizable Array Balanced Tree Linked List
Set
Interfaces
HashSet
List
Map
TreeSet
ArrayList, Vector
HashMap,
Hashtable
LinkedList
TreeMap
Hashtable x HashMap
 LinkedList x ArrayList x Vector
 TreeSet implements SortedSet
 TreeMap implements SortedMap

Wrapper implementations
Collections decorator
//Synchronization
public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static SortedMap synchronizedSortedMap(SortedMap m);
//Unmodifiable
public static Collection unmodifiableCollection(Collection c);
public static Set unmodifiableSet(Set s);
public static List unmodifiableList(List list);
public static Map unmodifiableMap(Map m);
public static SortedSet unmodifiableSortedSet(SortedSet s);
public static SortedMap unmodifiableSortedMap(SortedMap m);

Convenience Implementations

Arrays
 asList
 binarySearch

Collections
 nCopies
(immutable)
 singleton (immutable)
Algoritmos

Sorting




Shuffling


Collections.sort(list)
Arrays.sort(array)
Optimized merge sort (log n)
Collections.shuffle(list)
Routine Data Manipulation





Collections.reverse(list)
Collections.fill(list,value)
Collections.copy(detination,source)
Arrays.fill(array,value)
System.arrayCopy(dest,destPos,src,srcPos,length)
Algoritmos

Searching
 Collections.binarySearch(list,value)
 Arrays.binarySearch(array,value)

Finding Extreme Values
 Collections.max(list)
 Collections.min(list)
Customizando Implementações

Possíveis objetivos


AbstractCollection (bag)


Positional methods
AbstractSequencialList (uses linked list)


iterator, size
AbstractList (uses array)


iterator, size
AbstractSet


Persistência, Aplicação específica, Concorrência, Performance,
Funcionalidade, Conveniência, Adaptação
listIterator, iterator
AbstractMap

EntrySet view, put
Resolvendo Problemas Comuns

Refer to:
 http://java.sun.com/docs/books/tutorial/collecti
ons/problems/index.html
Referências

Joshua Bloch, The Java Tutorial,
Collections Framework, available at
http://java.sun.com/docs/books/tutorial/
collections/