Chapter7
Un article de Sometimes Kitties Think Too.
Sommaire |
Chapter7
Comparisons of Objects
+ '==' - only good for seeing if references are to same object
+ equals() - is for objects.
Wrapper classes return false unless object is of same class even though
values may be the same. Default Object implementation of
equals() is the same as '=='
public boolean equals(Object obj) {
return (this == obj);
}
Wrapper equals() implementation:
public boolean equals(Object obj) {'
return (obj instanceof Integer
&& intValue() == ((Integer) obj).intValue());
}
+ Must override equals() if objects are to be used for Hashs
**************************************************************** Equals() Contract **************************************************************** + reflexive a.equals(b) and b.equals(a) + symmetric a.equals(b) and b.equals(a) + transitive a.equals(b), b.equals(c) so a.equals(c) + consistent + x.equals(null) is false if x is non-null ****************************************************************
+ reflexive: a.equals(b) and b.equals(a)
+ symmetric: a.equals(b) and b.equals(a)
+ transitive: a.equals(b) and b.equals(c) then a.equals(c)
+ Always override equals() with a public method
********************************
HashCode() Contract
********************************
1) consistency
2) if 2 objects are equal then their HashCode is the same
3) if 2 objects are unequal then their HashCodes DO NOT have to be different
********************************
Signature:
public int hashCode()
1) a.hashCode() always returns same value
2) a.equals(b) means a.hashCode() == b.hashCode()
+ Object's hashCode() method returns a different hashCode for each instance
+ Byte and String override equals() and hashCode()
Collections
Interfaces:
Collection
List
Queue
Set
SortedSet
Map
SortedMap
Classes:
Maps:
HashMap
HashTable
TreeMap
LinkHashMap
Sets:
HashSet
LinkedHashSet
TreeSet
Lists
ArrayList
Vector
LinkedList
Queues
PriorityQueue
Utilities
Collections
Arrays
+ not all collections in the Collections Framework implement the Collection intf
e.g. Map-related classes do not implement Collection intf
Collections Framework Interfaces
Collections ----> List, Queue Set ----> Map SortedSet ----> SortedMap
Hierarchy
*Collection*
------------------------
/ | \
/ | \
V V V
*Set* *List* *Queue*
-------- ------- -------
/ | \ / | \ | \
/ | (Sorted / | \ | \
/ | Set) / | \ | \
/ | | / | \ | \
LinkedHashSet Hash Tree | | \ | \
Set Set | | LinkedList PriorityQueue
/ |
/ |
/ |
ArrayList Vector
*Map*
--------------------------------
/ / | \
/ / | \
/ / | \
Hashtable LinkedHashMap HashMap TreeMap
*Object* - interface
+ java.lang.Collections (with an 's') contains static collections utilities
+ collections methods include add(), remove(), contains(), size(), iterator()
Lists ----> lists of things, duplicates allowed Sets ----> unique things, NO DUPLICATES Maps ----> things with unique ids Queues ----> things arranged in the order they are to be processed
definitions:
ordered - able to be iterated through in non-random order
sorted - order determined by certian rules. For custom objects, sorting happens when Comparable interface is implemented
List - indexed
ArrayList - growable array, supports fast random access
Vector - same as arraylist but has synchronized methods
LinkedList - ordered, doubly linked list. Good for fast insertions/deletions. Implements Queue interface, supports Queue methods
Set - doesn't allow duplicates
HashSet - unsorted, unordered set
LinkedHashSet - ordered HashSet with doubly-linked list
TreeSet - sorted collections. Red-black tree
Map - unique identifiers
HashMap - unsorted, unordered. Allows 1 null key and many null values. Method put(key, value)
HashTable - synchronized HashMap. Nothing can be null
LinkedHashMap
TreeMap
Queue - FIFO interface
PriorityQueue - ordered by natural order or by Comparator
| List - are indexed |
----------------------------------------------------------------------------------
ArrayaList - growable array, supports fast iteration and random access
Vector - same as arraylist but has synchronized methods. Prehistoric
LinkedList - ordered, doubly linked list. Good for fast insertions/deletions.
Implements Queue interface, supports Queue methods
|
|---|---|
| Set - doesn't allow duplicates, duplicates determine by equals() |
---------------------------------------------------------------------------------- HashSet - unsorted, unordered set. Relies on hashCode() for insertion LinkedHashSet - ordered (by insertion sequence) HashSet with doubly-linked list TreeSet* - sorted collections. Red-black tree. Sorted by natural order |
| Map - unique identifiers |
---------------------------------------------------------------------------------- HashMap - unsorted, unordered. Allows 1 null key and many null values HashTable - synchronized HashMap. *Nothing can be null* Prehistoric LinkedHashMap - maintains insertion order. Faster iteration than HashMap TreeMap* - sorted Map. Use Comprarator or Comparable to define order |
| Queue - FIFO interface |
---------------------------------------------------------------------------------- PriorityQueue* - ordered by natural order or by Comparator. Sorted by "to-do" order |
Legend:
- sorted
<<>> interface
+ must override hashCode() with HashSet and LinkedHashSet otherwise the default hashCode will allow for duplicate insertions
Using Collections
+ ArrayLists - can grow dynamically and have insert/search methods
* instantiate polymorphically
* "coding to an interface"
+ AutoBoxing - collections don't hold primitives, but Java5 will autobox them for you
+ enhanced for loop can be used to iterate over all Collection types, including Sets
e.g.
Set h = new HashSet();
for (Object o: h) { }
Sorting Collections using java.util.Collections
+ Sorting - use Collections.sort(E e, Comparator c)
+ List must implement Comprable interface to be sorted this includes a single method compareTo()
+ equals(Object o) versus compareTo(E e)
Comprable Interface
int x = object1.compareTo(object2)
return values:
1) negative if object1 < object2
2) 0 if object1 == object2
3) positive if object1 > object2
Comparator Interface
+ required to implement "compare()"
+ can use Collections.sort(E e, Comparator c) also
public int compare(E e, E e)
Comparable vs Comparator
+ Comprable results in only one sort sequence
+ Comprable used by String, Wrapper, Date, etc...
+ Comparator more for 3rd party classes and results in many sequences
Sorting using java.util.Arrays
Arrays.sort(Array a)
Arrays.sort(Array a, Comparator c)
+ !! primitives always use a natural sort order so cannot use a Comparator with primatives
+ sort() methods are static
+ objects in a collection must be mutually comprable to be sorted
Searching
+ searches performed by
- Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)
- Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
- successful search returns index of element being searched
- unsuccessful searches return index of insertion point (using negative numbers)
result: ( -(insertion point) - 1)
++ collection/array must be sorted before searching
+ if collection you are searching was sorted using a Comparator, must sort using the same Comparator
Converting between Arrays & Lists
java.util.Arrays <T> List<T> asList( T[] )
- joins an array to a list, updates happen simultaneously
- arrays use array[index] syntax while lists use List.set(index, value) syntax
java.util.Collection Object[] toArray()
java.util.Collection <T> T[] toArray(T[] a)
- returns either Object[] or the array you specify (as toArray() arg)
Using Lists
+ LinkedList, ArrayList allow duplicates + iterate over list using Iterator
boolean hasNext()
returns TRUE if at least one more object to traverse
Object next()
returns next object in the collection AND moves forward
+ if call iterator like Iterator<E e> then no need to cast return object
Using Sets
+ insertion into sets return a boolean value indicating success or failure
+ usually sets accept heterogeneous object types
+ that is, unless the set is sorted (TreeMap/TreeSet) in which case objects have to be mutually comparable
+ add() method of TreeSet (and put of TreeMap) throws ClassCastException if elements of Set/Map cannot be compared. Elements need to
implement the Comparable interface. This is a RTException, not compiler error
Using Maps
+ any class inserted into a Map must override equals() and hashCode()
Enums by default override equals() and hashCode()
+ 2 steps in the HashMap retrieval
1) use hashCode() to find bucket
2) use equals() to find obj in the bucket
Map.entrySet() - returns a set of mapping pairs. Each element is of type Map.Entry
e.g.
for (Map.Entry pairs: map.entrySet()) {}
Using PriorityQueues
+ FIFO. Objects ordered by natural order or Comparator
peek() - returns highest priority element in queue w/o removing it
poll() - returns/removes hightest priority element
offer() - inserts element in PQ
Methods in Arrays & Collections
java.util.Arrays:
static List asList(T[])
static int binarySearch(Object[], key)
static int binarySearch(T[], key, Comparator)
static boolean equals(Object[], Object[])
static void sort(Object[])
static void sort(T[], Comparator)
static String toString(Object[])
java.util.Collections
static int binarySearch(List, key)
static void reverse(list)
static Comparator reverseOrder()
static void sort(List)
Methods for Lists, Maps, Queues
List Set Map
===================================================================
add(elem) add(elem) put(key, value)
add(index, elem)
-------------------+------------------+------------------
contains(elem) contains(elem) containsKey(elem)
containsValue(elem)
-------------------+------------------+------------------
indexOf(elem) keySet()
iterator() iterator()
-------------------+------------------+------------------
remove(index) remove(elem) remove(key)
remove(elem)
-------------------+------------------+------------------
size() size() size()
-------------------+------------------+------------------
toArray() toArray()
Generics
- Generics mostly used for enforcing type saftey on collections
- pre-Java5 you always had to cast the objects returned from a collection
- Java5 - compiler error if you put the wrong type in
- compiler warning if you pass an generic collection to a non-type safe method
- the typing information doesn't exist on the JVM (type erasure)
- arrays are different because they have compile-time and runtime protection
Polymorphism & Generics
The syntax is: Class<base type>
- List<parent> mylist = new ArrayList<child> DOES NOT WORK - no polymorphism for base types
- methods cannot accept subtypes of a generic supertype
--> e.g. method(ArrayList<Animal>) CANNOT accept ArrayList<Dog>
even though a non-typed ArrayList (with Dog elements) could go
into method that takes a parameter list of (ArrayList a)
- this works for regular arrays because of the Runtime exception: ArrayStoreException
- the problem with generics is that there's type erasure
- <? extends Class>
- contract for specifying a generic with an implicit promise not add to collection
- here "extends" means sub-classes or implementing interfaces
- no adding is allowed (except null)
- adding is only a special case of changing any generic variable of that class.
- <? super Class>
- accepts anything of Class or higher in the inheritance tree. In this case you can add to the collection
- assign any collection that is the Class or higher,
- but adding is only allowed for type Class (or lower of course), even if the list
itself has a higher type as generic parameter.
- <?>
- alone, means that can't add anything to the collection declared w/this wildcard
- List<? extends Object> and List<?> are identical
- wildcards can only be used for reference declarations, NOT for creating new collections (e.g. only for arguments, variables, return types, etc..)
- Backwards compatibility allows a generic collection to be cast to a raw type:
e.g.
List<Integer> li = new ArrayList<Integer>();
List rl = li;
or
Vector v = new Vector<Integer>();
Generic Declarations
+ generics can be used for non-collections. + Convention is to use "E" for element, "T" for type (although can use other letters) + class definitions for generics
e.g. public class This<T>
or
public class This<T extends That>
Generic Methods
+ methods can use generics, however, if class doesn't specify type, then must be declared in method
e.g. public <T> void thisMethod(T t) { }
+ common mistake is to use a wildcard vs a <T> or <E> in class/method declaration wildcards are only for reference variables!!
e.g. ILLEGAL:
public void <? extends Object> something()
or
public class Something<? extends Object>
+ when using generics in method declaration, must go after access modifiers but before return type:
public <T> void Method(T t) { }
NOT
<T> public void Method(T t) { }
- Cannot use static modifier for generics variables or methods:
e.g.ILLEGAL:
static T myObject;
static void myMethod() { T t1 = new T();}
static T myMethod2() {}
Questions
1. How are HashSet's useful? (since there are no keys)
2. Are default non-transient variable is set to 0 when de-serialized????
3. What happens when a duplicate is inserted into a Set?
Nothing, just won't add it. Will return false.
4. Why is List<String> more powerful than String[] (grow dynamically, insertion/search methods)
5. WHat is type erasure ???
it's the compiler erasing any information regarding generics types before making runtime code
6. Since HashMaps use the hashcode/equals test, doesn't it ultimately have to be the same exact object to be "found". Isn't that the point of comparisons?
References
[Collection Insertion Order]
