Transcript Hashtables - Systems and Computer Engineering

94.204* Object-Oriented Software
Development
Unit 8
Hashtables
(Case Study of Using and Overriding
Methods Inherited from Class Object)
•
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
revised January 2002
1
Class Object
• Comparing, copying and printing are just
three of the behaviours defined in the class
Object.
• There are other behaviours that only
become apparent as your programming
experience broadens.
• Example :
public native int hashCode();
– We must first introduce hashtables, then
discuss how we should override
hashCode() from class Object.
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
2
Tables
• A table is a collection of pairs of items
(key, value)
• When you put a value in the table, you
associate the value with a key
• To retrieve a value from the table, you
provide a key, and the table looks up and
returns the value associated with the key
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
3
Example
• An FGR posted outside the Registrar’s
office:
keys
Student #
Grade
107312
B+
168904
A+
values
...
221655
B-
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
4
Example
• A departmental telephone directory
keys
Name
Ext.
Homer
1786
Marge
8113
values
...
Lisa
4321
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
5
Java's Hashtable Class
• The Java API provides class Hashtable
in package java.util
– (note the lower-case "t". Yes, this is
inconsistent with the normal Java
naming conventions.)
public class Hashtable
extends Dictionary
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
6
Example
• Suppose we want to keep a table of
employee records
– each employee has an ID number,
which will be used as the key
Employee ID Employee
98765
:Employee
id=98765
…
Employee engineer = new
Employee();
engineer.setID( "98765“ );
Question : Employee ID is the key AND part of the
value. Why don’t we just use a list of Employee
objects?
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
7
Java.util.Hashtable Constructors
public Hashtable();
public Hashtable
(int initialCapacity,
float loadFactor);
public Hashtable
(int initialCapacity);
• In our example :
Hashtable staff = new
Hashtable();
// According to JBuilder,
// a default capacity=101
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
8
java.util.Hashtable put()
public Object put
(Object key, Object value)
• put() associates a value (any object)
with a key (an object), and stores the value
in the hash table
– later, we will discuss how to design a
class so that its instances can be used as
keys
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
9
java.util.Hashtable put()
• Keys must be unique
– You cannot store two values with the
same key. If you call put() twice with
the same key, the second value replaces
the first value
– put() uses the equals() method of the
key object to compare
– put() returns the previous value
stored with that key. If put() returns a
non-null value, you know that you have
replaced a previous entry
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
10
java.util.Hashtable put()
In our example :
String id = engineer.getID();
Object old =
staff.put( id, engineer );
if (old != null)
{
// id over-wrote oldID
String oldId = (String)old;
…
}
// or simply:
if (staff.put(
engineer.getID(),
engineer ) != null)
{…
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
11
java.util.Hashtable get()
public Object get(Object key)
• get() returns the value associated with
the specified key, and leaves the value in
the table
– get() returns null if the table does not
contain a value associated with the
specified key
• To retrieve information about an employee,
we need to know the key (the employee
ID):
String s = "98765";
Object o = staff.get( s );
if ((o != null) &&
(o instanceof Employee))
{
Employee e = (Employee)o;
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
12
java.util.Hashtable Search Methods
public boolean contains
( Object value)
• contains() returns true if the hash
table contains the specified value
Employee e2 = new Employee(…);
if ( staff.contains( e2 ) { … }
// Uses Employee#equals() to compare e2
// to all employee records stored in the
// table
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
13
java.util.Hashtable Search Methods
public boolean containsKey
( Object key )
• containsKey() returns true if the hash
table contains the specified key
if ( staff.containsKey( “98765”) ) { … }
// Uses String#equals() to compare
// “98765” to all keys used in the table.
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
14
More java.util.Hashtable methods
public Object remove(Object
key)
Deletes a key/value association from the
table
public void clear();
Clears table so it has no keys
public int size();
Returns the number of entries in the table
public boolean isEmpty();
Returns true if the table is empty
And the methods inherited from Class Object:
public boolean equals(Object o)
public String toString();
public Object clone();
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
15
More java.util.Hashtable Methods
• Tables are not “ordered” like lists. We
cannot index through the elements.
Can’t do this
for (i=0;i<staff.size();i++)
Employee e=(Employee)staff.get(i)
public Enumeration keys();
public Enumeration elements();
• Return Enumeration objects to allow you
to iterate through the complete set of keys
or values stored in a table
• We will discuss enumerations (or iterators)
later , but a quick example is given
Enumeration e = staff.elements();
while (e.hasMoreElements() )
{Employee e = (Employee)e.nextElement();}
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
16
Hash Table Theory
• Consider how we could implement the
FGR or dept. phone list tables
• If we used an array or linked list to store
key/value pairs, retrieving a value would
require a sequential search through the
keys
– for large tables, this is inefficient
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
17
Hash Table Theory
• Think of a hash table as an array of
“buckets”
• When we pass a key object to a hash table
object, the table asks the key to compute its
hash code
public native int hashCode();
• The hash code is used as the index into the
array (it selects one bucket), and the
key/value pair is stored in the bucket
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
18
Storing Key/Value Pairs in a
java.util.Hashtable Object
• e.g., add key/value objects k1/v1 to the
hash table: ht.put(k1, v1);
ht 0
1
k1
v1
2
3
...
k1.hashCode() == 1
99
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
19
Storing Key/Value Pairs in a
java.util.Hashtable Object
• e.g., add key/value objects k2/v2 to the
hash table: ht.put(k2, v2);
ht 0
1
2
k1
v1
k2
v2
3
...
k2.hashCode() == 3
99
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
20
Storing Key/Value Pairs in a
java.util.Hashtable Object
• e.g., add key/value objects k1/v3 to the
hash table: ht.put(k1, v3);
k1
ht 0
v3
replaces k1/v1
1
2
k2
v2
3
...
k1.hashCode() == 1
99
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
21
Hash Table Theory: Collisions
• What if two different key objects compute
the same hash code?
• We say that there is a collision (multiple
key/value pairs should be stored in the
same bucket)
• This can be handled several ways, but a
common approach is “chain” all key/value
pairs with the same hashcode (i.e., the
bucket is a linked list of key/value pairs)
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
22
Storing Key/Value Pairs in a
Hashtable Object
• e.g., add key/value objects k3/v4 to the
hash table: ht.put(k3, v4);
ht 0
k1
v3
k2
v2
k3
v4
1
2
3
...
k3.hashCode() == 1
99
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
23
Retrieving Values From a Hashtable
Object
•
•
•
•
ht.get(k1); returns v3
ht.get(k2); returns v2
ht.get(k3); returns v4
ht.get(k4); returns null
– no such key in the hash table
Facilities for minimizing collisions :
• protected void rehash();
– Resizes & re-organizes the hashtable
• The Load Factor
• A measure of “how full” the table is.
• Default = 0.75
• Set as argument in constructor
• Rehash() is automatically called
when this threshold is reached
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
24
Retrieving Values From a Hashtable
Object
• Value retrieval is efficient
– get() asks the key that is passed to it
to compute its hash code
– if the table contains a value associated
with that key, it must be in the bucket
that is selected by the hash code
– get() has to search at most one
bucket (list) for the specified key
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
25
What Objects Can Be Used As Keys?
• If a class overrides equals() and
hashCode() as appropriate for the class,
instances of the class can be used as keys
in a Hashtable
public native int hashCode()
• Extract from the javadoc page for
Object:
– “Returns a hash code value for the
object. This method is supported for the
benefit of hashtables such as those
provided by
java.util.Hashtable.”
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
26
hashCode()
“The general contract of hashCode is:
– Whenever it is invoked on the same
object more than once during an
execution of a Java application, the
hashCode method must consistently
return the same integer. This integer
need not remain consistent from one
execution of an application to another
execution of the same application.
– If two objects are equal according to the
equals method, then calling the
hashCode method on each of the two
objects must produce the same integer
result.”
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
27
Using Strings as Keys
• Why did our employee example work ?
– If you look at the javadoc page for class
String, you’ll see that it overrides
hashCode()and equals()
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
28
Designing hashCode()
• If you want to use instances of one of your
classes as keys in a hashtable, that class
will have to provide a hashCode()
method.
• Approach 1: Write your own
hashCode() method
– study the theory that underlies
designing a good hashing function and
write the method from scratch (not that
difficult to do, but beyond the scope of
this course)
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
29
Designing hashCode()
• Approach 2: Delegation
– if your class has an association or
aggregation relationship with an object
that implements hashCode(),
forward the hashCode() message to
it, and use the value returned by the
object; e.g.,
class SomeClass {
HashableClass o;
...
public int hashCode()
{
// return o’s hash code as
mine
return o.hashCode();
}
…
}
Copyright © 2002, Systems and Computer Engineering,
Carleton University. 94.204-08-Hashtable.ppt
30