Handbook of Data Structures and Applications, 2nd Edition

9

Hash Tables*

Pat Morin

Carleton University

9.1 Introduction

9.2 Hash Tables for Integer Keys

Hashing by Division•Hashing by Multiplication• Universal Hashing•Static Perfect Hashing• Dynamic Perfect Hashing

9.3 Random Probing

Hashing with Chaining• Hashing with Open Addressing•Linear Probing•Quadratic Probing•Double Hashing•Brent’s Method• Multiple-Choice Hashing•Asymmetric Hashing•LCFS Hashing•Robin-Hood Hashing•Cuckoo Hashing

9.4 Historical Notes

9.5 Other Developments

Acknowledgments

References

9.1Introduction

A set abstract data type (set ADT) is an abstract data type that maintains a set S under the following three operations:

1.INSERT(x): Add the key x to the set.

2.DELETE(x): Remove the key x from the set.

3.SEARCH(x): Determine if ...