COS30016 Programming in Java
COS70002 Software Development in Java
10 More Advanced Collections
Random, HashMap, HashSet
Based on Barnes and Kolling Chapter 5
Adapted by Rob Allen
Content
The bouncing-ball system
The tech-support system
HashMap
HashSet
Learning Objectives
Students should be able
to recognize and use Java constants
to use class Random
to use simple Java Collection classes:
ArrayList (as an example of List),
HashMap (as an example of Map),
HashSet (as an example of Set)
(c) Barnes & Kolling
Bouncing ball example
Chapter 5: bouncing-balls
y-axis
Each ball object has
diameter
x,y position (top left corner)
ySpeed
color
etc
groundPosition
(c) Barnes & Kolling
Object diagram
Section 5.13
A class variable
ie static
Instance variables
(c) Barnes & Kolling
Constant
private static final int GRAVITY = 3;
private: access modifier, as usual, often public
static: class variable
final: constant
type
Usually upper-case name
Must give value
(c) Barnes & Kolling
Bouncing ball code
public void move()
called every 50ms, ie 20/sec
{
erase(); // remove from canvas at the current position
// compute new position
ySpeed += GRAVITY;
yPosition += ySpeed;
xPosition += 2;
All in pixels
// check if it has hit the ground
if (yPosition >= (groundPosition - diameter) && ySpeed > 0) {
yPosition = (int)(groundPosition - diameter);
ySpeed = -ySpeed + ballDegradation;
}
ballDegradation is 2 and
is loss of speed at
bounce
draw(); // draw again at new position
}
(c) Barnes & Kolling
bounce!
(int) unnecessary
7
The Technical Support System
A textual, interactive dialog system
Idea based on Eliza by Joseph Weizenbaum (MIT,
1960s)
Setup, main loop,
shows response
Reads strings from console
(c) Barnes & Kolling
Analyses input strings,
generates a response
SupportSystem: main loop structure
boolean finished = false;
while(!finished) {
do something
if( exit condition ) {
finished = true;
A common
iteration pattern.
}
else {
do something more
}
}
(c) Barnes & Kolling
Main loop body first version
while ( !finished ) {
String input = reader.getInput();
if(input.startsWith("bye")) {
finished = true;
}
Another String method
else {
public boolean startsWith(
String prefix)
String response =
responder.generateResponse(input);
System.out.println(response);
}
}
Later Strings startsWith() will be
replaced by HashSetss contains().
(c) Barnes & Kolling
10
Useful String methods
charAt(int pos)
indexOf(String target)
contains(String target)
endsWith(String target)
substring(int first, int length)
toUpperCase()
trim()
split(String regex)
Reminder: strings are immutable!
(c) Barnes & Kolling
11
Responder
Ignores input randomly chooses a response from a list
also used in final version when doesn't find a keyword
private
ArrayList<String> defaultResponses;
private void fillDefaultResponses()
{
defaultResponses.add("That sounds odd. Could you
describe that problem in more detail?");
defaultResponses.add("No other customer has ever
complained about this before. \n" +
"What is your system configuration?");
. . .
}
(c) Barnes & Kolling
(Actually an array
could be used here.)
12
Responder: use of Random
private
Random randomGenerator;
public Responder()
{ ...
randomGenerator = new Random();
}
private String pickDefaultResponse()
{
int index =
randomGenerator.nextInt( defaultResponses.size() );
return defaultResponses.get(index);
}
int num = randomGenerator.next(); // a random 32-bit number
int n = randomGenerator.nextInt(100); // random in range 0..99
Choose
one:
0
(c) Barnes & Kolling
(size 1)
13
More sophisticated behaviour
Section 5.6: tech-support-complete
Responder
checks if individual words of input
correspond to (possibly) relevant messages
uses a Set of input words
HashSet<String>
uses a Map to perform the lookup
HashMap<String,String>
(c) Barnes & Kolling
14
Using Sets
import java.util.HashSet;
...
HashSet<String> mySet = new HashSet<String>();
mySet.add("one");
mySet.add("two");
mySet.add("three");
No change to mySet
"two" already present.
mySet.add("two");
for(String element : mySet) {
do something with element
}
(c) Barnes & Kolling
Compare with code
for an
ArrayList!
15
InputReader: tokenising String
private Scanner reader;
...
public HashSet<String> getInput()
{
System.out.print("> ");
String inputLine =
reader.nextLine().trim().toLowerCase();
String[] wordArray = inputLine.split(" ");
HashSet<String> words = new HashSet<String>();
for(String word : wordArray) {
words.add(word);
}
return words;
}
(c) Barnes & Kolling
Contains the unique
words in one line of user
input..
16
Maps
Maps are collections that contain pairs of values.
Pairs consist of a key and a value.
Lookup works by supplying a key, and retrieving a
value.
Example: a telephone book.
:HashMap
(c) Barnes & Kolling
"Charles Nguyen"
"(531) 9392 4587"
"Lisa Jones"
"(402) 4536 4674"
"William H. Smith"
"(998) 5488 0123"
17
Using a map
HashMap <String, String> phoneBook =
new HashMap<String, String>();
phoneBook.put("Charles Nguyen", "(531) 9392 4587");
phoneBook.put("Lisa Jones", "(402) 4536 4674");
phoneBook.put("William H. Smith", "(998) 5488 0123");
//later:
String phoneNumber = phoneBook.get("Lisa Jones");
System.out.println(phoneNumber);
(c) Barnes & Kolling
18
List, Map and Set
The Java Collections framework defines bundles of
methods Java interfaces
and implementing classes
List
ArrayList, LinkedList
Set
HashSet, TreeSet
Map
HashMap,
(c) Barnes & Kolling
19
Hashed collections
HashMap and HashSet are unordered collections
Very fast storage and retrieval
Speed is independent of the size of the collection.
Faster than the older class HashTable (which has protection
for multi-thread systems)
Require unique keys, and a hashCode() method
which can return distinct integers based on the key
is a method of Object so all Java classes have
a version String's version is excellent
hashCode()
The hash values are used as indexes into an internal
array
20
Hashing
Elements are scattered around an array,
not in order of key
Data is scattered into
short lists
K3,V3
key
array index
K1,V1
K6,V6
K4,V4
K2,V2
index = key.hashCode() % arraySize
simplified
21
Responder: using HashMap
private HashMap<String,String> responseMap;
...
public Responder()
{ ...
Key
Value
responseMap = new HashMap<String,String>();
fillResponseMap(); ...
}
private void fillResponseMap()
{
responseMap.put("crash",
"Well, it never crashes on our system. It must have
something\n" + "to do with your system. Tell me more about
your configuration." );
responseMap.put("crashes",
"Well, it never crashes on our system...
...
}
(c) Barnes & Kolling
22
Responder: using HashMap (contd)
public String generateResponse(HashSet<String> words)
{
for (String word : words) {
Key
String response = responseMap.get(word);
if(response != null) {
return response;
}
Value
}
null means no value is
stored for that key
Reach here if no value
found for any word
return pickDefaultResponse();
}
ArrayLists get vs
HashMaps get
(c) Barnes & Kolling
23
Exercises & reading
Exercises:
Modify Responder so it cannot randomly choose the same response as
last time.
What happens when you add (put) to a Map, another entry with the same
key?
How do you print out all the keys of a Map?
Set has a method contains() that depends on the element class having a
good version of equals(). Explain.
Reading:
Barnes & Kolling 5.1 - 5.9
(c) Barnes & Kolling
24
