L24-25 Colecciones

8/18/2009

Java Collections Framework Object Oriented Programming Colecciones

2

The Java Collection API • • • • • • •

General features Generics and parameterization Overriding equals() and hashCode() Enumerations Defining generic abstract types For each control structure For-each Autoboxing

1

8/18/2009

General-Purpose Implementation classes

Collections Framework • Collection – Generic container, most of the framework implements this

• List – stores multiple items in an explicit order (repeated elements allowed) – ArrayList, LinkedList, etc.

The primary implementations of the collection interfaces. • HashSet : Hash table implementation of the Set interface. • TreeSet : Red-black tree implementation of the SortedSet interface. • ArrayList : Resizable-array implementation of the List interface. – (Essentially an unsynchronized Vector.) The best all-around implementation of the List interface.

• Set – stores unique items in no particular order – HashSet, SortedSet, etc.

•

– May provide better performance than the ArrayList implementation if elements are frequently inserted or deleted within the list. – Useful for queues and double-ended queues (deques).

• Map – stores unordered key-value pairs (like a dictionary; keys are unique) – HashMap, Hastable, TreeMap, etc. Buena práctica: – No exponer tipos de datos usados innecesariamente • E.g., declare Map, instancie un HashMap()

Collection Operation • Collections typically provide these operations: – – – – – – –

add(Object o) – add an object to the collection remove(Object o) – remove the object clear() – remove all objects from collection size() () – returns a count of objects j in collection isEmpty() – returns true if collection is empty iterator() – traverse contents of collection contains(Object element); // use equals() for comparison

• Some operations are optional • Some operations are slower/faster

LinkedList : Doubly-linked list implementation of the List interface.

•

HashMap : Hash table implementation of the Map interface. – (Essentially an unsynchronized Hashtable that supports null keys and values.) The best all-around implementation of the Map interface.

•

TreeMap : Red-black tree implementation of the SortedMap interface.

Generic Types • Antes de Java 5, se podía recorrer una lista como sigue: public String concat(ArrayList list) { int i; StringBuffer buff = new StringBuffer(); for (i = 0; i< list.size(); i++) { String element = (String) lista.get(i); buff.append(element); } return buff.toString(); }

• Qué problema hay? ……. Casting?

2

8/18/2009

Generic Types • A partir de Java 5 • public String concat(List<String> list) { StringBuffer buff = new StringBuffer(); for (String element : list) { buff.append(element); pp } return buff.toString(); • } •

Arraylist, Generics • Crear un ArrayList usando Generics: – ArrayList listA = new ArrayList();

• Añadir elementos al ArrayList – listA listA.add(new add(new Integer(i)); – listA.add(new Integer(i+1)); – O – listA.add(1);

//Gracias a Autoboxing

Es código más corto y garantiza que el tipo de datos de la lista es String, además no requiere casting

Arraylist in a program • Buscar por un Object y retornar su posición int locationIndex = listA.indexOf("Jeff"); ( );

Arraylist in a program • Check to see if the List is empty: System.out.println("Is List A empty? " + li listA.isEmpty()); tA i E t ())

3

8/18/2009

The Set Interface

Set - API

• Is a Collection that cannot contain duplicate elements.

• Almost everything has been done for you • Union of two sets – Use:

• Models the mathematical set abstraction.

• Intersection of two sets – Use:

• Two Set objects are equal if they contain the same elements.

• Difference of two sets (A – B) – Use: • boolean removeAll(Collection c)

– boolean addAll(Collection c) – boolean b l retainAll(Collection t i All(C ll ti c))

• Two direct implementations: – HashSet

TreeSet

The Set Interface • Contains no methods other than those inherited from Collection. – Same signatures but different semantics ( meaning ) – – – – –

Collection c = new LinkedList(); Set s = new HashSet(); String o = “a”; c.add(o); c.add(o) ; // both return true; c.size() == 2 s.add(o); s.add(o) ; // 2nd add() returns false; s.size() == 1

Practica • Dado un arreglo de Strings, añada todos los elementos a un Set e imprima los duplicados a medida que los va añadiendo • String[] palabras={“Hay”, “una””, “una” , “pal”} Set s = new HashSet();

• It adds the restriction that duplicate elements are prohibited. – Collection noDups = new HashSet(c); // a simple way to eliminate duplicate from c

4

8/18/2009

Using Both ArrayList and Sets

Iterator (alternatative way) • • • • • • •

// you must create iterator for set Iterator<String> iter2 = firstnames.iterator(); // use iterator to print elements in set while (iter2.hasNext()) { System.out.println(iter2.next()); }

• You may want to use a set to get rid of duplicates, then put the items in an ArrayList and sort them! • Problem: – Often data comes in the form of an array – How o do we e go from o array a ay to ArrayList ay st o or TreeSet? eeSet

• Problem: – Often we are required to return an array – How do we go from a Collection such as an ArrayList or TreeSet to an array?

• Can do it the “hard” way with loops or iterators: • OR:

Converting from array to Collection • For arrays of objects (such as Strings) use the asList method in the Arrays class. • This returns a fixed-size list backed by the specified array • Pass this into the constructor of your ArrayList or set • Example • String[] words = String[N]; • . . . • TreeSet<String> wordset = new • TreeSet<String>(Arrays.asList(words));

Converting from Collection to array • Collections such as ArrayLists and TreeSets have a toArray method – This returns an array – Sintax: a bit awkward

• Example • • • • • •

TreeSet<String> wordset = new TreeSet<String>(); . . . String[] words = (String[]) wordset.toArray(new String[0]); or return (String[]) wordset.toArray(new String[0]);

5

8/18/2009

The Map interface // Bulk Operations void putAll(Map t); //optional void clear(); // optional // Collection Views; // backed by the Map, change on either will be reflected on the other. public Set keySet(); // cannot duplicate by definition!! public Collection values(); // can duplicate public Set entrySet(); // no equivalent in Dictionary // nested Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); }}

Basic Operations • Map m = new HashMap();

• • • • • •

................ Put in a key y and its value m.put(”Forbes”, ”Strawberry”); Get a value for a key val = m.get(”Forbes”); Change value for key m.put(”Forbes”, ”Coffee Mocha”);

Map • Keys map to values • Map<String, String> m = new TreeMap<String, String>();

Map example public class Birthday { public static void main(String[] args){ Map<String, Integer> m = new HashMap<String, Integer>(); m.put("Newton", new Integer(1642)); p ( , new Integer(1809)); g ( )); m.put("Darwin", System.out.println(m); } } Output: {Darwin=1809, Newton=1642}

35

6

8/18/2009

Map Iterator Example public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>( ); map.put( "One", 1); map.put("Two", 2); map.put( "Three",3); // get the set of keys and an iterator Set<String> keys = map.keySet( ); Iterator<String> It t <St i > it iter = k keys.iterator( it t ( ) ); // sequence through the keys and get the values while (iter.hasNext()){ String key = iter.next(); System.out.println(key + ", " + map.get(key)); } } // --- Output -Three, 3 One, 1 Two, 2

Iterator public static void printHashMap(HashMap hashMap) { System.out.print( "HashMap: " ); Iterator iterator = hashMap.entrySet().iterator(); while (iterator.hasNext()) (iterator hasNext()) { Map.Entry entry = (Map.Entry) iterator.next(); System.out.print( "(" + entry.getKey() + ": " + entry.getValue() + "), " ); } System.out.println(); }

HashSet vs treeSet (and HashMap vs TreeMap) • HashSet/ HashMap is much faster (constant time vs. log time for most operations), but offers no ordering guarantees. • always use HashSet/HashMap unless you need to use the operations in the SortedSet, SortedSet or in-order in order iteration iteration. • choose an appropriate initial capacity of your HashSet if iteration performance is important. – The default initial capacity is 101, and that's often more than you need. – can be specified using the int constructor. – Set s= new HashSet(17); // set bucket size to 17

7