Lecture 17.
Today we continued with hashing. We
encountered through an example the issue of collisions, that is, two or more
keys hashing to the same location. We saw two distinct ways to handle
collisions: separate chaining, and open addressing.
Separate chaining tacks a list
(initially empty) to every hash table cell. When a collision occurs items are
added to the list.
Separate chaining
is easy to analyze and implement and appears to perform quite favourably with
the open addressing schemes. However the main drawback is that by using pointers
and dynamic storage allocation we incur additional overhead. Thus separate
chaining is not often used in
practice.
Open addressing deals
with collisions in situ. When a collision occurs an alternate place in the hash
table is used to accommodate the newly inserted item. Today we saw the most
natural open addressing scheme, that is, linear probing.
On Friday we will look at some
other open addressing schemes.
Posted: Wed - February 16, 2005 at 03:50 PM