Hash Tables (Algorithms)

I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This video is part of my first-year Algorithms course.

The Hash Table is a data structure that implements the Dictionary ADT, but without any of the extra frills of predecessor, successor, min and max that we saw with the various search trees. In exchange for this more spartan API, it provides higher performance, with insertion and retrieval having usually constant cost instead of logarithmic (provided the table is properly dimensioned).

I explain the concept of hashing and two alternative strategies for storing items in a hash table: chaining, which is easier to understand, and open addressing, which is more space-efficient because it does not waste any space to store pointers.

In the case of open addressing we must pay attention to various subtleties regarding collisions and probing sequences, particularly when deleting items from the table.

Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.

Course web page:

Course handout:

My home page: