O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

9

Hash Tables*

Pat Morin

Carleton University

9.1 Introduction

9.2 Hash Tables for Integer Keys

Hashing by DivisionHashing by MultiplicationUniversal HashingStatic Perfect HashingDynamic Perfect Hashing

9.3 Random Probing

Hashing with ChainingHashing with Open AddressingLinear ProbingQuadratic ProbingDouble HashingBrent’s MethodMultiple-Choice HashingAsymmetric HashingLCFS HashingRobin-Hood HashingCuckoo 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required