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 (java.util.Hashtable)
https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html

"A"

The Java HashMap class (an alternative)

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

Page 7 of 34
 The Java Hashtable class: String Example

import java.util.*;
...
Hashtable<String, String> myTable = new Hashtable<String, String>();
myTable.put(“China”, “Beijing”);
myTable.put(“UK”, “London”); key value

Page 8 of 34
 myTable.put(“France”, “Paris”);
System.out.println(myTable.get(“China”)); //the output is “Beijing”);
System.out.println(myTable.get(“France”)); //the output is “Paris”);
System.out.println(myTable.get(“#$afr 33”)); //the output is null);

Page 9 of 34
Put and Get data into Hash Table in Java

import java.util.*;
- The class is defined in java.util
- (Alternatively, you can write java.util.Hashtable 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>();

myTable.put(606618, “Colour Printer M01”);
myTable.put(622801, “Printer Ink Black MB01”);

System.out.println(myTable.get(606618)); //“Colour Printer M01”

System.out.println(myTable.get(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:
data.put(“015-5144088888-8”, a);
data.put(b.accountNumber, b);
And get it back from the hash table using the correct accountNumber as the

Page 14 of 34
key:
BankAccount x = data.get(“015-5144088888-8”);
System.out.println(x.accountNumber + “ ” + x.customerName + “ ” + x.balance);
//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>();
myTable.put(“India”, “Bombay”);
System.out.println(myTable.get(“India”)); //output “Bombay”;

System.out.println(myTable.remove(“India”)); //output “Bombay”,

//india entry removed
System.out.println(myTable.remove(“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 java.util.*;
…
Hashtable<String, String> mytable = new Hashtable<String, String>();

mytable.put("A", "Apple");
mytable.put("B", "Boy");
mytable.put("C", "Cat");

Page 18 of 34
//Continuing from last page
System.out.println("The Hashtable contains:");

Set<String> keys = myTable.keySet();

for (String nextKey : keys) {

String nextValue= myTable.get(nextKey);
System.out.println("Key=" + nextKey + " Value="+ nextValue);
}

Page 19 of 34
 Note:
Set<String> keys = myTable.keySet();
- Provides an unordered listing of all keys.

for (String nextKey : keys) {

String nextValue= myTable.get(nextKey);
System.out.println("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)!

table1.put("Principal", vp);
table1.put("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 < s.length(); i++)
hashcode = hashcode*MULTIPLIER + (int)
s.charAt(i);
return (int) Math.abs((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