11. Hash Tables

In This Chapter

Introduction to Hashing

Open Addressing

Separate Chaining

Hash Functions

Hashing Efficiency

Hashing and External Storage

A hash table is a data structure that offers very fast insertion and searching. When you first hear about them, hash tables sound almost too good to be true. No matter how many data items there are, insertion and searching (and sometimes deletion) can take close to constant time: O(1) in Big O notation. In practice this is just a few machine instructions.

For a human user of a hash table, this amount of time is essentially instantaneous. It’s so fast that computer programs typically use hash tables when they need to look up hundreds of thousands of items in less than a second (as ...

Get Data Structures & Algorithms in Python now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.