17
Searching for a Key
❐The data that’s attached to a
key can be found fairly
quickly.
Number 701466868
18
Searching for a Key
❐Calculate the hash value.
❐Check that location of the array
for the key.
Number 701466868
19
Searching for a Key
❐Keep moving forward until you
find the key, or you reach an
empty spot.
Number 701466868
20
Searching for a Key
❐Keep moving forward until you
find the key, or you reach an
empty spot.
Number 701466868
21
Searching for a Key
❐Keep moving forward until you
find the key, or you reach an
empty spot.
Number 701466868
22
Searching for a Key
❐When the item is found, the
information can be copied to
the necessary location.
Number 701466868
23
Deleting a Record
❐Records may also be deleted from a hash table.
24
Deleting a Record
❐Records may also be deleted from a hash table.
❐But the location must not be left as an ordinary
“empty spot” since that could interfere with searches.
25
Deleting a Record
❐Records may also be deleted from a hash table.
❐But the location must not be left as an ordinary
“empty spot” since that could interfere with searches.
❐The location must be marked in some special way so
that a search can tell that the spot used to have
something in it.
26
❐Hash tables store a collection of records with keys.
❐The location of a record depends on the hash value
of the record’s key.
❐When a collision occurs, the next available
location is used.
Summary
27
To finish things off, I have hard copies of the next five slides. I tell the
students that these are some records of my past students and I want to
Kathy Martin
817339024
Took Data Structures in Fall 1993.
Grade A.
Hard worker. Always gets things done
on time.
28
Will Smith
506643973
Took Data Structures in Fall 1995.
Grade A.
29
William “Bill” Clinton
330220393
Took Data Structures in Fall 1995.
Grade B-.
30
Elizabeth Windsor
092223340
Took Data Structures in Fall 1995.
Grade B-.
31
Al Einstein
699200102
Took CSCI 2270 in Fall 1995.
Grade F.
32
Presentation copyright 1997 Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright