COM1102
Programming and Data Structures
Chapter 8
Hash Tables (Part A)
Page 1 of 34
What are Hash Tables
The next Data Structure that we learn is called a
Hash Table.
Key Value
001 “Simon So”
008 “Ng Sheung Tong”
003 “Ng Hup Gaat”
Operations:
Enter (put) a value with its associated key.
Look up (get) a value in the table using the key.
Page 2 of 34
What are Hash Tables
The ‘value’ can be any data type or objects.
Each key is unique (no two entries can have the same
key)
Different keys can have the same value
Key Value
“Apple” “A type of fruit”
“Zoo” “A place that with many animals to see”
“Java” “An island in Indonesia”
“Orange” “A type of fruit”
Page 3 of 34
What are Hash Tables
Key Value
SQUARE
TRIANGLE
CIRCLE
DIAMOND
The hash table will decide where (i.e., which position in
the table) to store a piece of data.
The caller cannot control the order and the position in
the table that the entries are actually stored.
Page 4 of 34
Hash Tables Operations
Put
Insert the value for a key into the table.
If an old value exists for the same key, the old value
will be replaced by the new value.
Note: Users do not and need Key Value
not) know the position of the
value in the table!
"S190012" "A" PUT
Key Value
Page 5 of 34
Hash Tables Operations
Get
Note: Users do not and need not know how the
value for a particular key is found in the table.
Key Value
key
Get
"S190012"
Page 6 of 34
The Java Hashtable class ([Link])
[Link]
"A"
The Java HashMap class (an alternative)
[Link]
Page 7 of 34
The Java Hashtable class: String Example
import [Link].*;
...
Hashtable<String, String> myTable = new Hashtable<String, String>();
[Link](“China”, “Beijing”);
[Link](“UK”, “London”); key value
Page 8 of 34
[Link](“France”, “Paris”);
[Link]([Link](“China”)); //the output is “Beijing”);
[Link]([Link](“France”)); //the output is “Paris”);
[Link]([Link](“#$afr 33”)); //the output is null);
Page 9 of 34
Put and Get data into Hash Table in Java
import [Link].*;
- The class is defined in [Link]
- (Alternatively, you can write [Link] every time)
Hashtable<String, String> myTable = new Hashtable<String, String>();
- Again, Java Generics let us handle different data type.
- (In this case, both the key and the value are String).
Page 10 of 34
Example
Key: Serial Number (integer number)
Value: Product Name (text)
Hashtable<Integer, String> myTable = new Hashtable<Integer, String>();
[Link](606618, “Colour Printer M01”);
[Link](622801, “Printer Ink Black MB01”);
[Link]([Link](606618)); //“Colour Printer M01”
[Link]([Link](622801)); // “Printer Ink Black MB01”
Page 11 of 34
In the above examples, both the keys and values
are simple strings or integers.
What if the values consist of more than one piece
of data?
For example, we want to use the account num-
ber as the key, and use it to store/retrieve both
the customer name and balance as values.
Page 12 of 34
Solution: store them in an object before saving into hash ta-
ble!
Example:
Key: Bank Account Number (numbers with spaces and hyphens)
Value: BankAccount Object
Hashtable<String, BankAccount> data = new Hashtable<String, BankAccount> ();
Where BankAccount is defined as in previous chapters:
Page 13 of 34
Let’s create the BankAc-
count objects first.
BankAc- count a = new
BankAc- count(“015-
5144088888- 8”, “Lu”,
8000.12);
BankAccount b = new BankAccount(“015-5144099999-9”, “Mary”, 1000.23);
Then, use the accountNumber as key, and the BankAccount object as value:
[Link](“015-5144088888-8”, a);
[Link]([Link], b);
And get it back from the hash table using the correct accountNumber as the
Page 14 of 34
key:
BankAccount x = [Link](“015-5144088888-8”);
[Link]([Link] + “ ” + [Link] + “ ” + [Link]);
//Note: x will refer to the same object as a
Page 15 of 34
Remove from a Hash Table
Remove is similar to find, except that the entry will be deleted
after returning to you.
Hashtable<String, String> myTable = new Hashtable<String, String>();
[Link](“India”, “Bombay”);
[Link]([Link](“India”)); //output “Bombay”;
[Link]([Link](“India”)); //output “Bombay”,
//india entry removed
[Link]([Link](“India”)); //output null;
Practice: Check out the Java API document yourselves to learn
more about the remove method.
Page 16 of 34
Looping through all keys and values in a Hash Ta-
ble
Suppose we want to loop through all keys and values in a
hashtable:
1. Obtain a Set of all keys in the table
2. Obtain each key from the set using an Enhanced for loop
a. For each next key
b. use the next key to find the value
c. print them out!
Page 17 of 34
Looping through all keys and values
import [Link].*;
…
Hashtable<String, String> mytable = new Hashtable<String, String>();
[Link]("A", "Apple");
[Link]("B", "Boy");
[Link]("C", "Cat");
Page 18 of 34
//Continuing from last page
[Link]("The Hashtable contains:");
Set<String> keys = [Link]();
for (String nextKey : keys) {
String nextValue= [Link](nextKey);
[Link]("Key=" + nextKey + " Value="+ nextValue);
}
Page 19 of 34
Note:
Set<String> keys = [Link]();
- Provides an unordered listing of all keys.
for (String nextKey : keys) {
String nextValue= [Link](nextKey);
[Link]("Key=" + nextKey + " Value="+ nextValue);
}
We can then use an enhanced for loop, and use a vari-
able nextKey to refer to each key in turn.
Page 20 of 34
Example: Create a table, and loop through all keys and values
Page 21 of 34
Time for a break!
(After the break: how does a hash table work: Part A)
Page 22 of 34
Page 23 of 34
How Does a Hash Table Work? (Part A)
But what are so special about Hash Tables?
How are the data stored inside tables?
How does it look up data?
How do they work?
Page 24 of 34
Looking up values in Hash Tables
Users do not and need not know how we search for the val-
ues.
Users don’t even know their position!
So how does a HashTable find the key and values?
The simplest strategy is Key Value
linear search.
But this is very inefficient!
"Principal"
"Principal"
Page 25 of 34
How do Hash Tables find the data quickly?
Value
They use a hash function to decide the posi- tion
of which a key is stored.
"Principal"
Hash Function 17
17
Hash code
A hash function is a function that reduces a search
key to an integer in a fixed range.
Page 26 of 34
Page 27 of 34
From the key, we use a hash function to calculate a hash code between 0 and (TableSize -1)
Value
"Principal"
Hash Function 17
17
The hash Hash code
code is then used as
the index of the value in the table.
Page 28 of 34
Sometimes the hash function returns the Value
same
hash code for two different keys.
Same hash code 17!
"Principal"
Hash Function 17
17
"Waiter"
Having two or more keys with identical hash code is
called collision.
Page 29 of 34
One solution is to link them up (like a linked list)!
[Link]("Principal", vp);
[Link]("Waiter", wp); Value
bucket
vp
"Principal"
Hash Function "Waiter" "Principal"
17 17
wp
"Waiter"
Page 30 of 34
Hash Function: Example
(Note: this is already handled by the Hashtable in Java)
private final long MULTIPLIER = –1664117991L;
private int Hash(String s, int nBuckets) {
long hashcode;
hashcode = 0;
for (int i=0; i < [Link](); i++)
hashcode = hashcode*MULTIPLIER + (int)
[Link](i);
return (int) [Link]((hashcode % nBuckets));
Page 31 of 34
}
Page 32 of 34
The previously shown hash function is typical of the func-
tions most often used in commercial applications.
The
mysterious
'w' 'a' 'i' 't' 'e' 'r' hashcode = 0; multiplier
hashcode = hashcode*MULTIPLIER + 119;
119 97 10 11 10 11 hashcode = hashcode*MULTIPLIER + 97;
5 6 1 4 hashcode = hashcode*MULTIPLIER + 105;
hashcode = hashcode*MULTIPLIER + 116;
hashcode = hashcode*MULTIPLIER + 101;
hashcode = hashcode*MULTIPLIER + 114;
Returned value: return hashcode % nBuckets;
between 0 and
(nBuckets – 1)
Page 33 of 34
How to choose a Multiplier?
Answer: This is beyond the scope of this course.
(We often use powers of 2 as multipliers. This leads to
faster computation in Java.)
Page 34 of 34