Lecture 18.
Today I summarized the section on
Hashing. We reviewed the different collision resolution techniques and discussed
each one's advantages and disadvantages.
We saw double hashing and
quadratic probing for the first time, so I discussed these methods in somewhat
more detail. In particular we saw how quadratic probing could be implemented
efficiently. We also discussed conditions that are necessary and sufficient so
that quadratic probing is guaranteed to find an empty table space and not cycle
infinitely looking for an empty space in a hash table that is not full.
Have a great Reading Week. On
February 28 we resume, and the topic will be priority queues and heaps, see
Chapter 21.
Posted: Fri - February 18, 2005 at 02:44 PM