Intro DS: Hashing


Of the data structures and techniques you will learn in this course, hashing is perhaps the most useful (and the most difficult of the concepts to grasp and master).

The following explanation of Hash Tables is taken from Wikipedia:

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.

In a well-dimensioned hash table, the average cost (number of instructions) for each look-up is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized[) constant average cost per operation.

In many situations, hash tables turn out to be more efficient than search trees or any other table look-up structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays,database indexing, caches, and sets.

A Better Explanation of Hashing

The previous explanation offered may have been a bit cryptic, so a video is in order: