Searching and Hashing

It is important to understand what search is and when it is appropriate. This page explains sequential and binary search, and their implementation. There is also the matter of hashing as a storage and search technique. In so doing, we introduce the unordered map and how to implement a map abstract data type using hashing. Read Sections 6.1-6.5. You may also find Sections 6.6-6.11 useful for practice.

1. Objectives

  • To understand what search is and when it is appropriate.

  • To be able to explain and to implement sequential search and binary search.

  • To understand the idea of hashing as a search technique.

  • To introduce the unordered map abstract data type.

  • To implement a map abstract data type using hashing.


Source: Runestone Academy, https://runestone.academy/runestone/books/published/cppds/SearchHash/toctree.html
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.