Introduction to Python Programming and Data Structures, 3rd Edition by Pearson

CHAPTER 21

Hashing

 

Objectives

• To know what hashing is for (§21.2).
• To use the hash function to obtain a hash code (§21.2).
• To handle collisions using open addressing (§21.3).
• To know the differences among linear probing, quadratic probing, and double hashing (§21.3).
• To handle collisions using separate chaining (§21.4).
• To understand the load factor and the need for rehashing (§21.5).
• To implement Map using hashing (§21.6).
• To implement Set using hashing (§21.7).

21.1 Introduction

Key Point

Hashing is super efficient. It takes O(1) time to search, insert, and delete an element using hashing.

The preceding chapters introduced search ...