Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A14 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A14 notes: Hash Tables

In this lecture

• Kruse 8
• Standish 11
• Langsam 7.4

• A Hash Table is an array.
• Each item which is to be inserted into the Hash Table has an unique key.
• A Hash function, hash, maps keys to positions in the Hash Table.
• To find an element in a Hash Table first look at position hash(key).
• To insert an element in a Hash Table first try position hash(key).

• Should map key values uniformly onto the positions in a Hash Table.
• Be easy to calculate.

• A collision is when to keys get mapped to the same position in the Hash Table.

The following table contains the probabilities that at least two people in group have the same birthday. This is equivalent to considering the probability that there is at least one collision in a table of size 365, given a number of entries in the table.

Number of People	Probability
10 20 30 40 50 60 70 80 90 100	0.11694818 0.41143838 0.70631624 0.89123181 0.97037358 0.99412266 0.99915958 0.99991433 0.99999385 0.99999969

Code for this lecture

/*  This is a simple hash function for character strings */
unsigned hash(char* s)
{
 int i = 0;
 unsigned value = 0;

 while (s[i] != ´\0´)
 {
   value = (s[i] + PRIME*value) % TABLESIZE;
   i++;
 }
 return value;
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:05:23