Lecture 20.
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. Just before leaving I
briefly describe double hashing.
On Friday we will continue
with double hashing and look at some other open addressing
schemes.
Posted: Wed - February 28, 2007 at 10:41 AM