1
❐Chapter 12 discusses
several ways of storing
information in an array, and
later searching for the
Hash Tables
2
This lecture introduces hash tables, which are an array-based method
What is a Hash Table ?
❐The simplest kind of hash
table is an array of records.
❐This example has 701
records.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
An array of records
. . .
[ 700]
3
What is a Hash Table ?
❐Each record has a special
field, called its key.
❐In this example, the key is a
long integer field called
Number.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
. . .
[ 700]
[ 4 ]
Number 506643548
4
What is a Hash Table ?
❐The number might be a
person’s identification
number, and the rest of the
record has information
about the person.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
. . .
[ 700]
[ 4 ]
Number 506643548
5
When a hash table is being used as a dictionary, some of the array
What is a Hash Table ?
❐When a hash table is in use,
some spots contain valid
records, and other spots are
“empty”.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 700]
Number 506643548
Number 233667136Number 281942902 Number 155778322
. . .
6
In order to insert a new entry, the key of the entry must somehow be
Inserting a New Record
❐In order to insert a new
record, the key must
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 700]
Number 580625685
7
There are many ways to create hash values. Here is a typical approach.
Inserting a New Record
❐Typical way create a hash
value:
Number 580625685
(Number mod 701)
What is (580625685 mod 701) ?
8
Inserting a New Record
❐Typical way to create a hash
value:
Number 580625685
(Number mod 701)
What is (580625685 mod 701) ? 3
9
Inserting a New Record
❐The hash value is used for
the location of the new
record.
Number 580625685
[3]
10
Inserting a New Record
❐The hash value is used for
the location of the new
record.
11
Collisions
❐Here is another new record
to insert, with a hash value
of 2.
Number 701466868
My hash
value is [2].
12
Collisions
❐This is called a collision,
because there is already
another valid record at [2].
Number 701466868
13
Collisions
❐This is called a collision,
because there is already
another valid record at [2].
Number 701466868
14
Collisions
❐This is called a collision,
because there is already
another valid record at [2].
Number 701466868
15
Collisions
❐This is called a collision,
because there is already
another valid record at [2].
16
Time for another quiz . . . Did anyone end up with a hash value of 700?
A Quiz
Where would you be placed
in this table, if there is no
collision? Use your social
security number or some
other favorite number.
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 700]
Number 506643548
Number 233667136Number 281942902 Number 155778322
Number 580625685 Number 701466868
. . .