Khalid Mughal Chapter 11

Page 1 of 61

Chapter 11. Collections and Maps Exam Objectives

hashCode() ! equals()"

Supplementary Objectives # $ Collection&Set&SortedSet&List&Map&SortedMap

%

' ' retainAll() (

$ Collection

)

addAll()&removeAll()&

*

' #

$ % HashSet&TreeSet&LinkedHashSet&ArrayList&Vector&LinkedList& HashMap&Hashtable&TreeMap&LinkedHashMap + ' &

&

'

$ $

,

#

UnsupportedOperationException

$

$

Collections *

,

Comparable

Comparator

-

$ $

Collections

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 2 of 61

+

$

11.1 The Collections Framework .

-

.

$

-

&

& /

$ %

java.util

$ ! $ 2

0

111

111"

$

2

.

!

&

&

111"

& $ . &

&

)

Core Interfaces )

Collection $ )

& 0

111

111

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 3 of 61

Collection . Set

2

Set

HashSet LinkedHashSet

Collection %

SortedSet

2

SortedSet

TreeSet

Set

$ List

2

List

Map

ArrayList Vector LinkedList

Collection

HashMap Hashtable LinkedHashMap

. $

SortedMap

62

&

Set List

0 $&

.

TreeMap

Map $

!

&

&

111 &

2

Map .

"

&

.

&

Collection # . $ SortedMap 2

& Map

Implementations *

java.util 0

113

$

&

114 5

$

Collection

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 4 of 61

$

& Collection

-

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 5 of 61

$

$ $

Map !

5 "

$

-

&

&

$

&

$ -

. Cloneable .

7

$

$

& 0 &

$

113 -

114

Serializable ) 113

$

! #

"

"

% $ &

HashSet

Set

'

5

equals() hashCode()

8

LinkedHashSet

Set

'

#

equals() hashCode()

8

TreeSet

SortedSet '

,

equals() compareTo()

ArrayList

List

.

#

equals()

LinkedList

List

.

#

equals()

Vector

List

.

#

HashMap

Map

'

(

)

$

equals()

(

)

$

5

equals() hashCode()

8

9$

equals() hashCode()

8

equals() hashCode()

8

$ LinkedHashMap

Map

' $

Hashtable

Map

'

. 5

$ TreeMap

SortedMap '

, $

$*

$

$*

equals() compareTo()

11.2 Collections

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 6 of 61

, $ UnsupportedOperationException java.util 113 113"

Collection &

!

Collection $

0

boolean

Basic Operations $

int size() boolean isEmpty() boolean contains(Object element) boolean add(Object element) boolean remove(Object element) add()

// Optional // Optional

remove()

$

true

false&

2

add()

&

$

-

contains() -

$

Bulk Operations

boolean containsAll(Collection c) boolean addAll(Collection c) boolean removeAll(Collection c) boolean retainAll(Collection c) void clear()

!

-

"

// // // //

Optional Optional Optional Optional

containsAll()

addAll()&removeAll()& retainAll() $ ) $:

' &

true

$ 0

11;

#

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 7 of 61

Array Operations $ Object[] toArray() Object[] toArray(Object a[]) $

toArray()

$ #

$ $& & $ # $

$

&

$#

&

$ null

&

$ $ &

$

$ $ ArrayStoreException

# )

$

$

Iterators .

. $

%

Collection

Iterator iterator() (

-

Iterator

%

Iterator boolean hasNext() (

true next()

$

. 2

Object next() 2 # NoSuchElementException

$

& &

Object remove()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 8 of 61

(

$

$ next()

next() & IllegalStateException& remove() $

# $

& next() UnsupportedOperationException

&

.

&

& $

$(

$

$

$

Iterator $

62

111

)

import java.util.*; public class IteratorUsage { public static void main(String[] args) { // (1) Create a list of Integers. Collection intList = new ArrayList(); int[] values = { 9, 11, -4, 1, 13, 99, 1, 0 }; for (int i = 0; i < values.length; i++) intList.add(new Integer(values[i])); System.out.println("Before: " + intList);

// (2)

Iterator interator = intList.iterator(); // (3) Get an iterator. while (interator.hasNext()) { // (4) Loop Integer element = (Integer) interator.next(); // (5) The next element int value = element.intValue(); if (value < 1 || value > 10) // (6) Remove the element if interator.remove(); // its value is not between 1 and 10. } System.out.println("After:

" + intList);

// (7)

} } <

%

Before: [9, 11, -4, 1, 13, 99, 1, 0] After: [9, 1, 1] 62

111 1 1=& - & Integer Collection &

2

,

ArrayList

$ - &

&

$ $ Object < $ *

int

int

+ &

toString()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

$

2

6/16/2006

Page 9 of 61

2

[

,

$

, ...,

] 2

$ . ! 3" 2

$ # 62

toString()

111&

! >"

toString()

toString()

! 4"

! ;" 2 $

instanceof +

! ?" # 2

$Integer 5

&

$ &

-

$

& , ConcurrentModificationException $

111 +

java.util $ $

$

62

$

$ $

remove() $

$ $

0 $

$

2 &

&

.

Review Questions

+

@

, Set Bag

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 10 of 61

LinkedList Collection Map

+

$

java.util

@

, HashList HashMap ArraySet ArrayMap TreeMap +

* @

, Collection Set SortedSet List Sequence

11.3 Sets '

Collection $

Set # 114" &

$ true&

& !

&

& add()

Set null addAll()

& false . Set -

"

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

add() !

Set

6/16/2006

Page 11 of 61

& +

#

*

,

#

a.containsAll(b)

b

a.addAll(b)

a = a

a.removeAll(b)

a = a – b!

a.retainAll(b)

a = a

a.clear()

a = C!

HashSet

a!

" b!

" "

b! $

" "

and LinkedHashSet

HashSet

.,

Set * 8 2 $!

. HashSet ! , equals() HashSet

LinkedHashSet & TreeSet& , 11A& ;?3" hashCode()

11>&

;A1"

& $

. HashSet HashSet SortedSet

*

equals() &

hashCode() #

&

$

$

.

LinkedHashSet & HashSet& 2

$ $

HashSet # HashSet& LinkedHashSet & &

'

LinkedHashSet

LinkedHashSet ! &

HashSet ! &

" $"

HashSet() B

&

$

HashSet(Collection c) B $

$

HashSet(int initialCapacity) B

&

$

$

HashSet(int initialCapacity, float loadFactor)

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 12 of 61

B

&

$(

$

$

)

import java.util.*; public class CharacterSets { public static void main(String[] args) { int numArgs = args.length; // A set keeping track of all characters previously encountered. Set encountered = new HashSet(); // (1) // For each program argument in the command line ... for (int i=0; i
// (2)

// (3) (4)

if (areDisjunct) System.out.println(characters + " and " + encountered + " are disjunct."); else { // Determine superset and subset relations. (5) boolean isSubset = encountered.containsAll(characters); boolean isSuperset = characters.containsAll(encountered); if (isSubset && isSuperset) System.out.println(characters + " is equivalent to " + encountered); else if (isSubset) System.out.println(characters + " is a subset of " + encountered); else if (isSuperset) System.out.println(characters + " is a superset of " + encountered); else System.out.println(characters + " and " + encountered + " have " + commonSubset + " in common."); } // Update the set of characters encountered so far. encountered.addAll(characters);

// (6)

} } }

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 13 of 61

(

%

java CharacterSets i said i am maids % [i] [d, [i] [a, [d, 62

and [] are disjunct. a, s, i] is a superset of [i] is a subset of [d, a, s, i] m] and [d, a, s, i] have [a] in common. a, s, m, i] is equivalent to [d, a, s, m, i] 113 %

#

$

-

&

&

$

&

&

$ D

&

& encountered ! 3" & &

& ! 4" ! ;" %

! 1" 0 characters&

&

&

// Determine whether a common subset exists. Set commonSubset = new HashSet(encountered); commonSubset.retainAll(characters); boolean areDisjunct = commonSubset.size()==0;

(4)

retainAll() 5 encountered characters # ) 7 & containsAll() ! ?"

! ;" )

// Determine superset and subset relations. boolean isSubset = encountered.containsAll(characters); boolean isSuperset = characters.containsAll(encountered); # 2

&

$

(5)

$

&

&

$ $

&

&

addAll()

! A" %

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 14 of 61 encountered.addAll(characters); 2 AbstractSet

// (6) $

toString() ! 0 113"

HashSet

11.4 Lists & 6

&

&

.)

2

$

# &

&

Collection % * & $

$ ) "

*

2

List & !

$

%

List

// Element Access by Index Object get(int index) (

2

<

Object set(int index, Object element) (

2

#

2

<

void add(int index, Object element) #

2# $

2

$ add(Object)

Object remove(int index)

$&

Collection

<

remove(Object)

2& Collection

$

<

boolean addAll(int index, Collection c) #

2& true

$

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 15 of 61

#

*

$ 2

& &

20 IndexOutOfBoundsException

size()-1 . 2

// Element Search int indexOf(Object o) int lastIndexOf(Object o) $

2 7

&

E1

// List Iterators ListIterator listIterator() ListIterator listIterator(int index) $& & $

2

interface ListIterator extends Iterator { boolean hasNext(); boolean hasPrevious(); Object next(); Object previous();

// Element after the cursor // Element before the cursor

int nextIndex(); int previousIndex();

// Index of element after the cursor // Index of element before the cursor

void remove(); void set(Object o); void add(Object o);

// Optional // Optional // Optional

} # 2 +

ListIterator

next()

previous() +

& remove()

Iterator & $ &

// Open Range-View List subList(int fromIndex, int toIndex) & 2toIndex-1 . .$

2fromIndex $ & :

ArrayList, LinkedList,

$

and Vector List

java.util

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

% ArrayList&

6/16/2006

Page 16 of 61

LinkedList&

Vector

ArrayList

List List $ )

$ F *

$

$

Vector Vector ArrayList $

$& $'

&

ArrayList

Vector $

& $*

LinkedList $ F 2 LinkedList%

# &

$* LinkedList

$ &

&

void addFirst(Object obj) void addLast(Object obj) Object getFirst() Object getLast() Object removeFirst() Object removeLast()

Vector $ $ ) ArrayList Vector LinkedList, & LinkedList *

&

ArrayList

/ 8 $*

Vector

-

*

* &

* + #

&

ArrayList

%

ArrayList ArrayList() B LinkedList

& $ArrayList . Vector

$

ArrayList(Collection c) B ArrayList

ArrayList $

$

ArrayList .

$

LinkedList

Vector

ArrayList(int initialCapacity) B

$(

&

)

$ArrayList Vector $

$.

*

import java.util.*;

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 17 of 61

public class TakeAGuess { final static int NUM_DIGITS = 5; public static void main(String[] args) { // Sanity check on the given data. if (args.length != NUM_DIGITS) { System.err.println("Guess " + NUM_DIGITS + " digits."); return; } /* Initialize the solution list. This program has a fixed solution. */ List secretSolution = new ArrayList(); // (1) secretSolution.add("5"); secretSolution.add("3"); secretSolution.add("2"); secretSolution.add("7"); secretSolution.add("2"); // Convert the user's guess from string array to list. List guess = new ArrayList(); for (int i=0; i
(2)

// Find the number of digits that were correctly included. List duplicate = new ArrayList(secretSolution); int numIncluded = 0; for (int i=0; i
(3)

/* Find the number of correctly placed digits by comparing the two lists, element by element, counting each correct placement. */ // Need two iterators to traverse through guess and solution. (4) ListIterator correct = secretSolution.listIterator(); ListIterator attempt = guess.listIterator(); int numPlaced = 0; while (correct.hasNext()) if (correct.next().equals(attempt.next())) numPlaced++; // Print the results. System.out.println(numIncluded + " digit(s) correctly included."); System.out.println(numPlaced + " digit(s) correctly placed."); } } (

%

java TakeAGuess 3 2 2 2 7 % 4 digit(s) correctly included. 1 digit(s) correctly placed. 62

114

* * String

-

2 secretSolution

add()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

& ! 1" &

6/16/2006

Page 18 of 61

guess&

! 3" $

$ &

! 4" guess remove()

get()

.

2 true

&

// Find the number of digits that were correctly included. List duplicate = new ArrayList(secretSolution); int numIncluded = 0; for (int i=0; i
$ guess

(3)

$ secretSolution

& %

// Need two iterators to traverse through guess and solution. ListIterator correct = secretSolution.listIterator(); ListIterator attempt = guess.listIterator(); int numPlaced = 0; while (correct.hasNext()) if (correct.next().equals(attempt.next())) numPlaced++;

(4)

Review Questions

' +

@

, , $ UnsupportedOperationException

UnsupportedOperationException

throws

. List . ArrayList Collection

$

2 get

- +

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

@

6/16/2006

Page 19 of 61

import java.util.*; public class Sets { public static void main(String[] args) { HashSet set1 = new HashSet(); addRange(set1, 1); ArrayList list1 = new ArrayList(); addRange(list1, 2); TreeSet set2 = new TreeSet(); addRange(set2, 3); LinkedList list2 = new LinkedList(); addRange(list2, 5); set1.removeAll(list1); list1.addAll(set2); list2.addAll(list1); set1.removeAll(list2); System.out.println(set1); } static void addRange(Collection col, int step) { for (int i = step*2; i<=25; i+=step) col.add(new Integer(i)); } } ,

$set2

TreeSet Comparator & UnsupportedOperationException

3?

. +

Collection

@

, add(Object o) retainAll(Collection c) get(int index)

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 20 of 61

iterator() indexOf(Object o) / +

@

import java.util.*; public class Iterate { public static void main(String[] args) { List l = new ArrayList(); l.add("A"); l.add("B"); l.add("C"); l.add("D"); l.add("E"); ListIterator i = l.listIterator(); i.next(); i.next(); i.next(); i.next(); i.remove(); i.previous(); i.previous(); i.remove(); System.out.println(l); }; }; , #

[A, B, C, D, E].

#

[A, C, E].

#

[B, D, E].

#

[A, B, D].

#

[B, C, E].

# 0 +

NoSuchElementException Collection @

true

, contains() add() containsAll() retainAll() clear()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 21 of 61

11.5 Maps . Map

$

G

$&

&

H 6 & &

$

& $ $

0

2

&

!

"

$

$ . 8

*

! $" &

. $

&

$ 2

Map & $

Collection $% $ &

&

$ #

Map UnsupportedOperationException java.util 113 0 114"

$ !

Map

Basic Operations $

$

Object put(Object key, Object value) #

Gkey&valueH $ $& $<

< #

$

&

null

Object get(Object key) (

$

&

$

null

Object remove(Object key)

< $

remove() $

$&

$<

$# &

null

boolean containsKey(Object key) (

$

true

boolean containsValue(Object value) (

true

2

$

int size() boolean isEmpty() !

&

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

$

"

6/16/2006

Page 22 of 61

$

Bulk Operations void putAll(Map t)

<

void clear()

< &

Collection Views Set keySet() Collection values() Set entrySet() B &

$& G

$

H

& Set&

values()

$5 $

Collection & 6

$ .

$ $

G

-

$

&

H Map.Entry

$

* 2

&



%$interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); }

HashMap, LinkedHashMap,

and Hashtable

0 114 LinkedHashMap&TreeMap& HashMap !

,

+

11A&

Map

Hashtable & ;?3"

HashMap * Collections $

java.util

*null !

% HashMap&

Hashtable

,

LinkedHashMap TreeMap

* $ $ * 11I& ;I1"

null $

$& *

Vector Map

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

Hashtable Hashtable $ $ Hashtable &

6/16/2006

Page 23 of 61

hashCode()

$

equals()

-

!

< ,

$ 11>&

;A1"

LinkedHashMap HashMap LinkedHashMap HashMap LinkedHashSet HashSet 6 HashMap ! HashSet" LinkedHashMap ! LinkedHashSet" $ & LinkedHashMap & & $ $ * & $ LinkedHashSet $J $ $ 2 ! " 8 & LinkedHashMap ! " & & & * $ * $ LinkedHashMap HashMap

& &

LinkedHashMap <

$ $

.

&

$

&

HashMap &

$< &

&

$

LinkedHashMap

HashMap&

$* * F $

0

$

)

LinkedHashMap& $8 &

$

HashMap&

2

toString() $

{

=

,

toString()

=

, ...,

=

} 2

$ .

-

$ &

toString()

$

& $

&

2 $

$

HashMap

% HashMap() HashMap(int initialCapacity) HashMap(int initialCapacity, float loadFactor) B

&

$HashMap&

$

HashMap(Map otherMap) B

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 24 of 61

LinkedHashMap HashMap

#

Hashtable &

LinkedHashMap %

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) B

&

$LinkedHashMap

&

$& true

false

$(

')

import java.util.*; public class WeightGroups { public static void main(String[] args) { // Create a map to store the frequency for each group. Map groupFreqData = new HashMap(); int numArgs = args.length; for (int i=0; i
file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

// (6) (7)

// (8)

// (9)

6/16/2006

Page 25 of 61

System.out.println(group + ":\t" + new String(bar)); } // end while } // end main() } // end of class (

%

>java WeightGroups 74 75 93 75 93 82 61 92 10 185 % 10: 60: 75: 80: 90: 95: 185:

* * *** * * ** *

62

11;

2

$

& 2

&

$

&

% #

& $

% ! 1"

! 3" &

&

&

! 4" ,

$&

$

& $

$ // Increment count, set to 1 if it's the first value of group. Integer oldCount = (Integer) groupFreqData.get(weightGroup); Integer newCount = (oldCount==null) ? new Integer(1) : new Integer(oldCount.intValue()+1); groupFreqData.put(weightGroup, newCount); #

$ ! keySet() ! ;" $ ! ?"

" $

// (3)

groupFreqData $& & sort() Collections

List keys = new ArrayList(groupFreqData.keySet()); Collections.sort(keys); # .

(2)

&

// (4) // (5)

$&

$

groupFreqData

$ ! A"

ListIterator keyIterator = keys.listIterator(); 0

$&

!

&

$

// (6) "

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

&

! >"

6/16/2006

Page 26 of 61

! I" // Current key (group). Integer group = (Integer) keyIterator.next(); // Extract count (value) from the map. Integer count = (Integer) groupFreqData.get(group); .

$

(7)

// (8)

fill()

&

Arrays

! K"

11.6 Sorted Sets and Sorted Maps ,

& ! Comparable Comparator

$ + J

SortedSet 0 113 &

Comparable

SortedMap& 114" < -

$ $

Comparator&

The Comparator Interface /

$

)

.

&

Comparator

% int compare(Object o1, Object o2) compare() ,

&) &

&

&

- & $&

$ equals()

!

,

11>"

The Comparable Interface .

$ L ./# & java.lang.Comparable

$

Comparable &String&Date& %

File&

int compareTo(Object o) &) & & ClassCastException $

&

#

- & -

,

$& equals()

!

,

11>"

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 27 of 61

< -

$ $ 5 !

-

String ,

1=?&

Collections.sort()

!

;13" ,

Character $ .

2

$

-

"

2 $

2 $ $

&

!

$ 1=4&

,

&

-

. $ 62

4KA" .

$ Collections Comparator ! ,

&

Comparator Arrays 11I& ;I3"

11? $

! ! 3" .

TreeSet

"6 2

! 4"

String compareTo() 2 2

$

&

! 1" &

String -

&

Comparable compareTo()

# )

CASE_INSENSITIVE_ORDER" ! 2

compare()

$

! 1" $

&

*

+

#

$

&

$ 2 &

0 &

"report"

&

0

2

& .

& B

"court"& 'o' $

'u' &

"report"

"court" B "court"&

$ 2 "troper"

$# 2

$

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

&"report" "truoc"

6/16/2006

Page 28 of 61

. $ 11?

$ ! ;"

compare() .

& &

! ?"

! A"

compareTo()

62

RhymingStringComparator

compare() & 2

$ ! 1" $

$(

-1

#

&

$

#

import java.util.*; public class ComparatorUsage { public static void main(String[] args) {

// //

// Choice of Set strSet = Set strSet = Set strSet =

comparator. new TreeSet(); // (1a) new TreeSet(String.CASE_INSENSITIVE_ORDER); // (1b) new TreeSet(new RhymingStringComparator()); // (1c)

// Add each command line argument to the set. for (int i=0; i < args.length; i++) { strSet.add(args[i]); } System.out.println(strSet);

// (2)

// (3)

} } class RhymingStringComparator implements Comparator { public int compare(Object obj1, Object obj2) {

// (4)

// (5) Create reversed versions of the strings. String reverseStr1 = new StringBuffer((String) obj1).reverse().toString(); String reverseStr2 = new StringBuffer((String) obj2).reverse().toString(); // Compare the reversed strings lexicographically. return reverseStr1.compareTo(reverseStr2);

// (6)

} } % >java ComparatorUsage court Stuart report Resort assort support transport distort <

! 1" %

[Resort, Stuart, assort, court, distort, report, support, transport] <

! 1" %

[assort, court, distort, report, Resort, Stuart, support, transport] <

$

! 1" %

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 29 of 61 [Stuart, report, support, transport, Resort, assort, distort, court]

The SortedSet Interface 2

SortedSet

$

Set

// Range-view operations SortedSet headSet(Object toElement) SortedSet tailSet(Object fromElement) SortedSet subSet(Object fromElement, Object toElement) &

headSet() $

, & subSet() fromElement&

$&

tailSet() & &

toElement& 2 $

5

// First-last elements Object first() Object last() $

first()

&

last()

$ $

NoSuchElementException // Comparator access Comparator comparator()

& & $

&

&

null $

The SortedMap Interface 2

SortedMap

Map

#

$ SortedSet

&

$ // Range-view operations SortedMap headMap(Object toKey) SortedMap tailMap(Object fromKey) SortedMap subMap(Object fromKey, Object toKey) // First-last keys Object firstKey() Object lastKey() // Comparator access Comparator comparator()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 30 of 61

TreeSet

and TreeMap

TreeSet $

TreeMap $ & $&

SortedSet

,

&

$ $8

&

$

& HashSet $

SortedMap

2 TreeSet

HashMap

6

)

TreeMap&

% TreeSet() TreeMap() .

$ $

$&

&

TreeSet(Comparator c) TreeMap(Comparator c) .

2

$

TreeSet(Collection c) TreeMap(Map m) .

& $&

$

TreeSet(SortedSet s) TreeMap(SortedMap m) . &

$(

.)

import java.util.*; public class WeightGroups2 { public static void main(String[] args) { // Create a map to store the frequency for each group. Map groupFreqData = new HashMap(); int numArgs = args.length; for (int i=0; i
file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 31 of 61 // Increment count, set to 1 if it's the first value of group. (2) Integer oldCount = (Integer) groupFreqData.get(weightGroup); Integer newCount = (oldCount==null) ? new Integer(1) : new Integer(oldCount.intValue()+1); groupFreqData.put(weightGroup, newCount); // (3) } /* Only the histogram for the weight groups between 50 and 150 is of interest. Print frequency for these groups in a sorted order. */ // Transfer the data to a sorted map. SortedMap sortedGroupFreqData = new TreeMap(groupFreqData);

// (4)

// Select the relevant sub-map. SortedMap selectedGroupFreqData = // (5) sortedGroupFreqData.subMap(new Integer(50), new Integer(150)); /** Print by traversing the sorted entries of weight groups (key) and count (value). */ Iterator entryIterator = selectedGroupFreqData.entrySet().iterator(); // (6) while (entryIterator.hasNext()) { Map.Entry entry = (Map.Entry) entryIterator.next(); // (7) // Extract groups (key) and count (value) from entry. Integer group = (Integer) entry.getKey(); Integer count = (Integer) entry.getValue(); int intCount = count.intValue();

(8)

/* Use the fill() method from the Arrays class to create a string consisting of intCount number of '*'. */ char[] bar = new char[intCount]; Arrays.fill(bar, '*');

// (9)

System.out.println(group + ":\t" + new String(bar)); } // end while } // end main() } // end of class (

%

java WeightGroups2 74 75 93 75 93 82 61 92 10 185 % 60: 75: 80: 90: 95:

* *** * * **

62 11;&

11A

#

2

62

% (

& $

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

62

11;

6/16/2006

Page 32 of 61

&

! ;"

SortedMap sortedGroupFreqData = new TreeMap(groupFreqData); B

// (4)

&

! ?"

SortedMap selectedGroupFreqData = // (5) sortedGroupFreqData.subMap(new Integer(50), new Integer(150)); ' ,

& !

entrySet() $

&

! A" 0 &

$

6 2

$

$ $ &

"

.

Iterator entryIterator = selectedGroupFreqData.entrySet().iterator(); - '

&

// (6)

6

$ Map.Entry

&

! I"

// Extract groups (key) and count (value) from entry. Integer group = (Integer) entry.getKey(); Integer count = (Integer) entry.getValue(); int intCount = count.intValue();

(8)

Review Questions

2 +

-

Map

@

, contains(Object o) addAll(Collection c) remove(Object o) values()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 33 of 61

toArray() 3 +

@

, $

values()

Set

B

$keySet()

Map .

2

Collection

$

. Map

$

+

@

import java.util.*; public class Lists { public static void main(String[] args) { List list = new ArrayList(); list.add("1"); list.add("2"); list.add(1, "3"); List list2 = new LinkedList(list); list.addAll(list2); list2 = list.subList(2, 5); list2.clear(); System.out.println(list); } } , [1, 3, 2] [1, 3, 3, 2] [1, 3, 2, 1, 3, 2] [3, 1, 2] [3, 1, 1, 2] 5 +

comparator()

@

,

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 34 of 61

ArrayList HashMap TreeSet HashSet TreeMap +

$

java.util.Map.Entry@

, Object getKey() Object setKey(Object value) void remove() Object getValue() void setValue(Object value)

11.7 Implementing the equals(), hashCode(), and compareTo() Methods -

$

*final -

#

&

$ compareTo()

#

< $ $

$

Object

hashCode() HashMap #

equals() & $ Comparable 113

equals() Comparable

hashCode() $

# HashSet )

-

.

2 & ! :5<"

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

. %

6/16/2006

Page 35 of 61

$ &

(

$

$

+

$ & $

$

The equals() Method #

$

-

&

$ -

Object

SimpleVNO #

$

$(

62 11> toString()

/4

equals() $#

6

$

equals() 2

5

Object

1

public class SimpleVNO { // Does not override equals() or hashCode(). private int release; private int revision; private int patch; public SimpleVNO(int release, int revision, int patch) { this.release = release; this.revision = revision; this.patch = patch; } public String toString() { return "(" + release + "." + revision + "." + patch + ")"; } } TestVersionSimple $# $

62 $

11I SimpleVNO SimpleVNO - &

. 62

2

SimpleVNO # & ! 1" &! 3" & ! 4" & versions& ! ;" 2 & $ test()

11I

+

downloads

$

! ?" & versions

62

11I

SimpleVNO equals()

-

& $

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

$ SimpleVNO -

6/16/2006

Page 36 of 61

$ $ latest 5

-

$ older& ! A" &! >" &! I" & false $ - & inShops $

latest $

-

$

equals() -

$&

&

,

& equals() & $ . (9.1.1) versions versions $ contains() List 2 &false . HashMap

$ $ $

false& 62

! K" $

SimpleVNO $ - & SimpleVNO -

11I&

$

List ! 1?" equals()

SimpleVNO

$ ,

inShops

! 1;" &

$ $ versions

$ $ $

vnoList& contains() &

Integer & downloads 8 $ ! 3=" , Object

! 1K" & & -

! 1>" & $ hashCode()

! 33" ! 34" & Comparable

$

SimpleVNO & !

2

,

compareTo()

11A& SimpleVNO

;?3" # -

& 2

& 8

&

+

$(

test()

0

62

11I

1

#6

equals()

import java.util.*; public class TestVersionSimple { public static void main(String[] args) { (new TestVersionSimple()).test(); } protected Object makeVersion(int a, int b, int c) { return new SimpleVNO(a, b, c); } protected void test() { // Three individual version numbers. Object latest = makeVersion(9,1,1); Object inShops = makeVersion(9,1,1); Object older = makeVersion(6,6,6);

// (1) // (2) // (3)

// An array of version numbers.

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 37 of 61 Object[] versions = { makeVersion( 3,49, 1), makeVersion( 8,19,81), makeVersion( 2,48,28), makeVersion(10,23,78), makeVersion( 9, 1, 1)};

// (4)

// An array of downloads. Integer[] downloads = { // (5) new Integer(245), new Integer(786), new Integer(54), new Integer(1010), new Integer(123)}; // Various tests. System.out.println("Test object reference and value equality:"); System.out.println(" latest: " + latest + ", inShops: " + inShops + ", older: " + older); System.out.println(" latest == inShops: " + (latest == inShops)); // (6) System.out.println(" latest.equals(inShops): " + (latest.equals(inShops))); // (7) System.out.println(" latest == older: " + (latest == older)); // (8) System.out.println(" latest.equals(older): " + (latest.equals(older))); // (9) Object searchKey = inShops; System.out.println("Search key: " + searchKey); System.out.print("Array: "); for (int i = 0; i < versions.length; i++) System.out.print(versions[i] + " "); boolean found = false; for (int i = 0; i < versions.length && !found; i++) found = searchKey.equals(versions[i]); System.out.println("\n Search key found in array: " + found);

// (10)

// (11)

// (12) // (13)

List vnoList = Arrays.asList(versions); // (14) System.out.println("List: " + vnoList); System.out.println(" Search key contained in list: " + vnoList.contains(searchKey)); // (15) Map versionStatistics = new HashMap(); // for (int i = 0; i < versions.length; i++) // versionStatistics.put(versions[i], downloads[i]); System.out.println("Map: " + versionStatistics); // System.out.println(" Hash code for keys in the map:"); for (int i = 0; i < versions.length; i++) // System.out.println(" " + versions[i] + ": " + versions[i].hashCode()); System.out.println(" Search key " + searchKey + " has hash code: " + searchKey.hashCode()); // System.out.println(" Map contains search key: " + versionStatistics.containsKey(searchKey)); // System.out.println("Sorted list:\n\t" + (new TreeSet(vnoList))); System.out.println("Sorted map:\n\t" + (new TreeMap(versionStatistics))); System.out.println("List before sorting: " + vnoList); Collections.sort(vnoList);

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

(16) (17) (18) (19)

(20) (21)

// (22) // (23) // (24)

6/16/2006

Page 38 of 61 System.out.println("List after sorting: " + vnoList); System.out.println("Binary search in list:"); // (25) int resultIndex = Collections.binarySearch(vnoList, searchKey); System.out.println("\tKey: " + searchKey + "\tKey index: " + resultIndex); } } <

%

Test object reference and value equality: latest: (9.1.1), inShops: (9.1.1), older: (6.6.6) latest == inShops: false latest.equals(inShops): false latest == older: false latest.equals(older): false Search key: (9.1.1) Array: (3.49.1) (8.19.81) (2.48.28) (10.23.78) (9.1.1) Search key found in array: false List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)] Search key contained in list: false Map: {(9.1.1)=123, (10.23.78)=1010, (8.19.81)=786, (3.49.1)=245, (2.48.28)=54} Hash code for keys in the map: (3.49.1): 13288040 (8.19.81): 27355241 (2.48.28): 30269696 (10.23.78): 24052850 (9.1.1): 26022015 Search key (9.1.1) has hash code: 20392474 Map contains search key: false Exception in thread "main" java.lang.ClassCastException ... .

$

equals() %0

$

%0

% $ true

self&self.equals(self)

$

x

y&x.equals(y)

$ y.equals(x)

true

true !

%0 $ x.equals(z) true

"

%0

x&y

$

x

&

null

%0

*null

equals()

x.equals(y)

y& -

$

z&

y.equals(z)

x.equals(y)

true&

$

$

obj&obj.equals(null)

$ false

#

'

Reflexivity

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 39 of 61

$ $% ==" $! %

-

&

# -

$

-

if (this == argumentObj) return true;

Symmetry 2

-

x.equals(y) equals() y.equals(x) equals() 2

x&

$ -

$

y #

& &$

equals() -

# .

$ $

equals() &

$

!

*

"

$

equals()

Transitivity #

&A

-

B&

&

& $B&

C

.

$

. $ equals()

$

$

equals()

&

equals()

$

%

return super.equals(argumentObj) && compareSubclassSpecificAspects(); $ equals() 8

*

&

2 $

$ -

&

equals() *

# $ &

$ $

#

equals() # $

equals() - & equals()

&

equals()

-

#

equals() $ $ $

equals() equals()

& #

equals() *

equals()

$

-

Consistency 0

$ !

-

"

! &

*

" 8

$

! &

* -

" &

equals()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 40 of 61

null

&

$

comparison -

null

equals() 2

false

7 $

$ 2

$

null

. $&

%

if (argumentObj == null) return false; #

$

& null%

#

instanceof

$

false

if (!(argumentObj instanceof MyRefType)) return false; &

$(

2

$

equals()

public class UsableVNO { // Overrides equals(), but not hashCode(). private int release; private int revision; private int patch; public UsableVNO(int release, int revision, int patch) { this.release = release; this.revision = revision; this.patch = patch; } public String toString() { return "(" + release + "." + revision + "." + patch + ")"; } public boolean equals(Object obj) { if (obj == this) return true; if (!(obj instanceof UsableVNO)) return false; UsableVNO vno = (UsableVNO) obj; return vno.patch == this.patch && vno.revision == this.revision && vno.release == this.release; }

// (1) // (2) // (3) // (4) // (5)

} 62

11K

equals() equals()

5 2&

Method overriding signature

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 41 of 61

$ public boolean equals(Object obj)

// (1) $ &

Object

%

public boolean equals(MyRefType obj)

// Overloaded.

B $ $

& B equals()

MyRefType %

MyRefType ref1 = new MyRefType(); MyRefType ref2 = new MyRefType(); Object ref3 = ref2; boolean b1 = ref1.equals(ref2); boolean b2 = ref1.equals(ref3); 8

& .

& $

B &

-

// True. Calls equals() in MyRefType. // Always false. Calls equals() in Object. $&

equals() &

$ equals()

MyRefType

Reflexivity test $ true

62

equals()

&

equals() 11K

! 3"

Correct argument type equals() instanceof

62

11K

$

-

! 4" &

%

if (!(obj instanceof UsableVNO)) return false;

// (3)

$&

null

false

obj

null instanceof UsableVNO # ! 4" - %

true

obj F 2

final& $

if ((obj == null) || (obj.getClass() != this.getClass())) return false; ! 4" this.getClass()) -

2

null

$

2

-

&

// (3a)

(obj.getClass() !=

#

&

-

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 42 of 61

Argument casting $ $

& %

*

62

instanceof ! ;"

11K

UsableVNO vno = (UsableVNO) obj;

// (4)

Field comparisons 6

0 #

$ -

$ & 11K

62

UsableVNO

$ $

: %

return vno.patch == this.patch && vno.revision == this.revision && vno.release == this.release; #

true&

0 2

& &

UsableVNO

// (5)

equals()

-

true

$

UsableVNO

0 &

productInfo& %

(vno.productInfo == this.productInfo || (this.productInfo != null && this.productInfo.equals(vno.productInfo))) 2

vno.productInfo == this.productInfo $ NullPointerException equals() & this.productInfo null -

62

* !

Double.doubleToLongBits()" 5.5 Double "

)

!

$ #

productInfo

$ & Float.floatToIntBits() * equals() Float

< $

& &

- & $

B &

0 * & & ! ?" 62 .

&

&

equals()

#

$ 2

$ &

& return

11K equals()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 43 of 61

62

111=

UsableVNO 62

62

11I

11K UsableVNO

equals()

$(

3

#6

equals()

public class TestVersionUsable extends TestVersionSimple { public static void main(String[] args) { (new TestVersionUsable()).test(); } protected Object makeVersion(int a, int b, int c) { return new UsableVNO(a, b, c); } } <

%

Test object reference and value equality: latest: (9.1.1), inShops: (9.1.1), older: (6.6.6) latest == inShops: false latest.equals(inShops): true latest == older: false latest.equals(older): false Search key: (9.1.1) Array: (3.49.1) (8.19.81) (2.48.28) (10.23.78) (9.1.1) Search key found in array: true List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)] Search key contained in list: true Map: {(10.23.78)=1010, (2.48.28)=54, (3.49.1)=245, (9.1.1)=123, (8.19.81)=786} Hash code for keys in the map: (3.49.1): 27355241 (8.19.81): 30269696 (2.48.28): 24052850 (10.23.78): 26022015 (9.1.1): 3541984 Search key (9.1.1) has hash code: 11352996 Map contains search key: false Exception in thread "main" java.lang.ClassCastException ... $

& UsableVNO

-

$ $ -

8 & HashMap& 0 ()

$ equals() UsableVNO & & equals()

&

$< -

-

&

0 hashCode() compareTo

The hashCode() Method

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 44 of 61

.

$ $& $

$

2

$ $

$

,

<

2 2

B $

% 8 #

$

5

&

( $ 8

$

#

*

%

$

#

$

& & $

$ $ &

0

&

&

* $

% $ .

$ $

. , 0

$&

$

2

.

& $

#

-

$ $&

$

* !

113" & Object

java.util

% -

hashCode() equals()

-

. UsableVNO

$ &

62

hashCode() 11K 6

$

B $

62 %

equals() $ 111=

Map: {(10.23.78)=1010, (2.48.28)=54, (3.49.1)=245, (9.1.1)=123, (8.19.81)=786}

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 45 of 61

hashCode() &

$

Object $ $

&

UsableVNO

-

$

%

Hash code for keys in the map: (3.49.1): 27355241 (8.19.81): 30269696 (2.48.28): 24052850 (10.23.78): 26022015 (9.1.1): 3541984 .

$! K11"

%

Search key (9.1.1) has hash code: 11352996 Map contains search key: false - & hashCode() Object $GK11&134H $GK11&134H& equals() < $ hashCode() % #

equals() & & $ - ! K11" $ - ! K11" $ $ UsableVNO $

General Contract of the hashCode() method %

hashCode() %

"

-

hashCode() 2 equals() $

$ -

&

2 $ % # equals() -

%# &

-

hashCode() equals() %#

% # equals() -

& #

-

hashCode() $

hashCode() -

5

$

-

5

-

&

-

Heuristics for implementing the hashCode() method 1111& # 62 ReliableVNO

hashCode() $ %

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 46 of 61 hashValue = 11 * 313 + release * 312 + revision * 311 + patch $ < $

!

-

,

D 4&

?KA" 6 equals() equals() &

hashCode()

$(

hashCode()

public class ReliableVNO { // Overrides both equals() and hashCode(). private int release; private int revision; private int patch; public ReliableVNO(int release, int revision, int patch) { this.release = release; this.revision = revision; this.patch = patch; } public String toString() { return "(" + release + "." + revision + "." + patch + ")"; } public boolean equals(Object obj) { if (obj == this) return true; if (!(obj instanceof ReliableVNO)) return false; ReliableVNO vno = (ReliableVNO) obj; return vno.patch == this.patch && vno.revision == this.revision && vno.release == this.release; }

// (1) // (2)

public int hashCode() { int hashValue = 11; hashValue = 31 * hashValue + release; hashValue = 31 * hashValue + revision; hashValue = 31 * hashValue + patch; return hashValue; }

// (6)

// (3) // (4) // (5)

} int ! 1"

sfVal

sf& %

public int hashCode() { int sfVal; int hashValue = 11; ... sfVal = ... // Compute hash value for each significant field sf. hashValue = 31 * hashValue + sfVal; // (1) ... return hashValue;

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 47 of 61 }

2 B

sfVal

$

sf

0

sf

boolean% sfVal = sf ? 0 : 1

0

sf

byte, char, short, or int% sfVal = (int)sf

0

sf

long% sfVal = (int) (sf ^ (sf >>> 32))

0

sf

float% sfVal = Float.floatToInt(sf)

0

sf

double% long sfValTemp = Double.doubleToLong(sf);

%

sfVal = (int) (sfValTemp ^ (sfValTemp >>> 32)) 0

-

sf $

$

equals()

$&

%$hashCode()

sfVal = ( sf == null ? 0 : sf.hashCode()) 0

$B

sf

$

0

2 $

0 hashCode() &

!

.

&

.

2

7 & equals()

int Boolean $ $

hashCode()

equals() equals() " $

2 public int hashCode() { return 1949; } .

0

$& -

0

$

boolean

& true

hashCode()

&

hashCode()

false

int& &

String 41&

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

$ &

6/16/2006

Page 48 of 61

0

2

&

"abc"

% hashValue = 'a' * 312 + 'b' * 311 + 'c' * 310 = 97 * 31 * 31 + 98 * 31 + 99 = 96354 0

- & hashCode() 62

! K11" ! K11" $

1113 $ $GK11&134H

-

&

ReliableVNO

62

< -

$ ! K11"

-

&

# $

$

1111 $

& $GK11&134H $ - ! K11"

$ equals() $

$

$(

#6

hashCode()

public class TestVersionReliable extends TestVersionSimple { public static void main(String[] args) { (new TestVersionReliable()).test(); } protected Object makeVersion(int a, int b, int c) { return new ReliableVNO(a, b, c); } } <

%

... Map: {(10.23.78)=1010, (2.48.28)=54, (3.49.1)=245, (8.19.81)=786, (9.1.1)=123} Hash code for keys in the map: (3.49.1): 332104 (8.19.81): 336059 (2.48.28): 331139 (10.23.78): 338102 (9.1.1): 336382 Search key (9.1.1) has hash code: 336382 Map contains search key: true Exception in thread "main" java.lang.ClassCastException ...

The compareTo() Method Comparable $

%

, 11A compareTo()

;?3 # < -

Comparable Comparable +

compareTo()

,

11A

;?3%

int compareTo(Object o) #

&)

&

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

-

&

6/16/2006

Page 49 of 61

& ClassCastException $ -

.

- &

#

-

compareTo() % 0

$

- &

- &

& $

. compareTo() obj2.compareTo(obj3) > 0& 0

-

$

-

!

" 0 2 & obj1.compareTo(obj2) > 0 obj1.compareTo(obj3) > 0 &

& &

compareTo() == 0) == (obj1.equals(obj2))

*)

compareTo() $ &(obj1.compareTo(obj2) -

$

7 compareTo()

$ . compareTo() #

equals() & compareTo()

equals() -

compareTo() # & $ compareTo() equals() & $

equals() $

equals() compareTo()

public boolean equals(Object other) { // ... return compareTo(other) == 0; } . 62

compareTo() 1114 &

0 2

final

$(

compareTo()

Comparable

public final class VersionNumber implements Comparable { private final int release; private final int revision; private final int patch;

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 50 of 61

public VersionNumber(int release, int revision, int patch) { this.release = release; this.revision = revision; this.patch = patch; } public String toString() { return "(" + release + "." + revision + "." + patch + ")"; } public boolean equals(Object obj) { if (obj == this) return true; if (!(obj instanceof VersionNumber)) return false; VersionNumber vno = (VersionNumber) obj; return vno.patch == this.patch && vno.revision == this.revision && vno.release == this.release; }

// (1) // (2)

public int hashCode() { int hashValue = 11; hashValue = 31 * hashValue + release; hashValue = 31 * hashValue + revision; hashValue = 31 * hashValue + patch; return hashValue; }

// (6)

public int compareTo(Object obj) { VersionNumber vno = (VersionNumber) obj;

// (7) // (8)

// (3) // (4) // (5)

// Compare the release numbers. if (release < vno.release) return -1; if (release > vno.release) return 1;

(9)

// Release numbers are equal, // must compare revision numbers. if (revision < vno.revision) return -1; if (revision > vno.revision) return 1; // Release and revision numbers are equal, // must compare patch numbers. if (patch < vno.patch) return -1; if (patch > vno.patch) return 1;

(10)

// All fields are equal. return 0;

(12)

(11)

} } compareTo() ClassCastException&

null

$ NullPointerException

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 51 of 61

! I"

62

1114 #

&

#

& $ $

5

$ $

$

* & ) ! K"

()

& 2

# compareTo

! 13"

62

1114

B

) ! K"

62

0

2

&

1114%

if (release < vno.release) return -1; if (release > vno.release) return 1; // Next field comparison $ %

&

int releaseDiff = release - vno.release; if (releaseDiff != 0) return releaseDiff; // Next field comparison int $ , <

62

# 2

*boolean > 0 compareTo()

111;

&

$ -

equals() compareTo()

'

&

TreeSet 62

111; $

62 $&

$(

'

1114 VersionNumber compareTo()

. &VersionNumber

-

System.out.println("Sorted list:\n\t" + (new TreeSet(vnoList))); System.out.println("Sorted map:\n\t" + (new TreeMap(versionStatistics))); $

62

VersionNumber 62 11I hashCode() &

&

111;

// (22) // (23)

compareTo() TreeSet& ! 33" & compareTo() . $& TreeMap& ! 34" & compareTo() $ compareTo()

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 52 of 61 public class TestVersion extends TestVersionSimple { public static void main(String[] args) { (new TestVersion()).test(); } protected Object makeVersion(int a, int b, int c) { return new VersionNumber(a, b, c); } } <

%

... Sorted list: [(2.48.28), (3.49.1), (8.19.81), (9.1.1), (10.23.78)] Sorted map: {(2.48.28)=54, (3.49.1)=245, (8.19.81)=786, (9.1.1)=123, (10.23.78)=1010} ... + Collections

' Arrays

$ ,

! 1;" $

$

java.util 62

11I 111;&

vnoList%

System.out.println("List before sorting: " + vnoList); Collections.sort(vnoList); System.out.println("List after sorting: " + vnoList);

// (24)

2

%

List before sorting: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)] List after sorting: [(2.48.28), (3.49.1), (8.19.81), (9.1.1), (10.23.78)] .

$

2 $

searchKey

62

! K11" &

111;%

int resultIndex = Collections.binarySearch(vnoList, searchKey); System.out.println("\tKey: " + searchKey + "\tKey index: " + resultIndex); 62

2

Key: (9.1.1)

$

%

Key index: 3

11.8 Working with Collections $% *

$ $

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 53 of 61

&

$

L

&2 $

)

Vector

*

Hashtable&

&

. .

-

&

#

$ &L #

$

&

#

$

$

& *

Collections

Synchronized Collection Decorators $ * static static static static static static

Collection List Map Set SortedMap SortedSet

)

Collections %

$

synchronizedCollection(Collection c) synchronizedList(List list) synchronizedMap(Map m) synchronizedSet(Set s) synchronizedSortedMap(SortedMap m) synchronizedSortedSet(SortedSet s)

.

$

$

)

&

&

*

$ // Create a synchronized decorator. Collection syncDecorator = Collections.synchronizedCollection(nonsyncCollection); # $

& )

$ %

)

&

// Each thread can only traverse when synchronized on the decorator. synchronized(syncDecorator) { for (Iterator iterator = syncDecorator.iterator(); iterator.hasNext();) doSomething(iterator.next()); }

Unmodifiable Collection Decorators $ $

$ static static static static static static

Collection List Map Set SortedMap SortedSet

Collections

*

%

unmodifiableCollection(Collection c) unmodifiableList(List list) unmodifiableMap(Map m) unmodifiableSet(Set s) unmodifiableSortedMap(SortedMap m) unmodifiableSortedSet(SortedSet s)

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 54 of 61

$ UnsupportedOperationException # #

$

&

&

$

&

$

Sorting Collections Collections static void sort(List list) static void sort(List list, Comparator comp)

$ !

,

11A"

Searching in Collections Collections static int binarySearch(List sortedList, Object obj) static int binarySearch(List sortedList, Object obj, Comparator comp) $

2

obj &

$

2 static static static static

Object Object Object Object

max(Collection max(Collection min(Collection min(Collection

%

c) c, Comparator comp) c) c, Comparator comp)

* $ ) $

&

B $ NoSuchElementException

$ $

Singleton Collections .

&

!

&

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

$

6/16/2006

Page 55 of 61

$& Collections

$"

$

&

$



%$static Set singleton(Object o) static List singletonList(Object o) static Map singletonMap(Object key, Object value)

0

2

&

$

%

// Create a singleton set with the element to remove. Set fishBone = Collections.singleton(bone); // bone is a fish part. // Remove the element fish.removeAll(fishBone); // fish is a set of fish parts. $

&

$

&

$

$

%

Collections.EMPTY_SET Collections.EMPTY_LIST Collections.EMPTY_MAP

$

Other Utility Methods in the Collections Class $Collection

List&

-

/

$

$

static void copy(List dst, List src) . static void fill(List list, Object o) ( static List nCopies(int n, Object o) B

n

-

static void reverse(List list) ( static Comparator reverseOrder() ( -

*

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

' $

6/16/2006

Page 56 of 61

-

)

KKnull

%

List itemsList = new ArrayList(Collections.nCopies(99, null));

2

$

Integer

%$&

*

Collections.sort(intList, Collections.reverseOrder()); Arrays.sort(strArray, Collections.reverseOrder()); % Collection intSet = new TreeSet(Collections.reverseOrder()); intSet.add(new Integer(9)); intSet.add(new Integer(11)); intSet.add(new Integer(-4)); intSet.add(new Integer(1)); System.out.println(intSet); // [11, 9, 1, -4] static void shuffle(List list) (

$

&

&

boolean replaceAll(List list, Object oldVal, Object newVal) (

oldVal

7

newVal

true

static void rotate(List list, int distance) (

$

.

static void swap(List list, int i, int j) ,

i

j

$

&

&

5

// intList denotes the following list: Collections.rotate(intList, 2); // Collections.rotate(intList, -2); // List intSublist = intList.subList(1,4);// Collections.rotate(intSublist, -1); // //

Two to the Two to the Sublist: One to the intList is

right. left. left. now:

[9, 11, -4, 1, 7] [1, 7, 9, 11, -4] [9, 11, -4, 1, 7] [11, -4, 1] [-4, 1, 11] [9, -4, 1, 11, 7]

Utility Methods in the Arrays Class Arrays $

$ &



%$$

&

&

$

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 57 of 61

Arrays

& $& $

asList() $ B $

asList()

$

List List ) Arrays

List List

toArray() $

Collection

static List asList(Object[] backingArray)

String[] jiveArray = new String[] {"java", "jive", "java", "jive"}; Set jiveSet = new HashSet(Arrays.asList(jivearray)); // (1) String[] uniqueJiveArray = (String[]) jiveSet.toArray(new String[0]); // (2) . ! 1" &

jiveArray toArray() $uniqueJiveArray

&

List& $

&

Set . ! 3" $

Abstract Implementations ! AbstractSet

java.util 0 113 114" 0 2 & & & &2 abstract $ & 2

HashSet AbstractCollection $ $ )

Review Questions

' D

-

$ $&

equals()

hashCode() @

String func(Object x, Object y) { return (x == y) + " " + x.equals(y) + " " + (x.hashCode() == y.hashCode()); } , "false false true" "false true false"

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 58 of 61

"false true true" "true false false" "true false true" - #

equalsImpl() equals()

public class Pair { int a, b; public Pair(int a, int b) { this.a = a; this.b = b; } public boolean equals(Object o) { return (this == o) || (o instanceof Pair) && equalsImpl((Pair) o); } private boolean equalsImpl(Pair o) { // ... PROVIDE IMPLEMENTATION HERE ... } } , return a == o.a || b == o.b; return false; return a >= o.a; return a == o.a; return a == o.a && b == o.b; . +

*

@

, ArrayList HashSet Vector TreeSet LinkedList

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 59 of 61

/ +

hashCode() @

import java.util.*; public class Measurement { int count; int accumulated; public Measurement() {} public void record(int v) { count++; accumulated += v; } public int average() { return accumulated/count; } public boolean equals(Object other) { if (this == other) return true; if (!(other instanceof Measurement)) return false; Measurement o = (Measurement) other; if (count != 0 && o.count != 0) return average() == o.average(); return count == o.count; } public int hashCode() { // ... PROVIDE IMPLEMENTATION HERE ... } } , return 31337; return accumulated / count; return (count << 16) ^ accumulated; return ~accumulated; return count == 0 ? 0 : average();

Chapter Summary

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 60 of 61

% %

java.util

$

$

& LinkedHashSet

HashSet

& $ArrayList&Vector&

Collection

$

$

Set

$ LinkedList

$

List

& $HashMap&LinkedHashMap& Comparator

$ Hashtable

$

$ TreeSet $

SortedMap

)

Map

Comparable &

SortedSet

$

$

)

$

$ TreeMap

$ Collections

Arrays

Programming Exercises

+ #

2

$ ,

& &

&

$

$

'

+

!

&

"( (

%

>java Concordance Hello World {d=[9], o=[4, 6], r=[7], W=[5], H=[0], l=[2, 3, 8], e=[1]}

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006

Page 61 of 61

file://C:\Documents and Settings\cdot\Local Settings\Temp\~hhAFF6.htm

6/16/2006