C++ Plus Data Structures, 6th Edition

CHAPTER 11: Sets, Maps, and Hashing

© Repina Valeriya/Shutterstock

Goals

After studying this chapter, you should be able to

• Describe a set at the logical level

• Implement a set both explicitly and implicitly

• Describe a map at the logical level

• Implement a map

• Define the following terms:

  • Hashing

  • Linear probing

  • Rehashing

  • Clustering

  • Collisions

• Design and implement an appropriate hashing function for an application

• Describe how to resolve collisions through linear probing, rehashing, and chaining

Up to this point, we have emphasized ADTs that arrange data into specific relationships with access operations that depend on their arrangement. For example, the stack is a linear arrangement of items with operations that support LIFO access. ...