Hash Tables

Learn How to Efficiently Search for Data in a List
Published

April 1, 2024

Exploration

  • Read chapter 15 in A First Course on Data Structures in Python
  • Explore hash table implementations in the ds2 package of donsheehy/datastructures. Can you conduct an experiment to evaluate different approaches to mapping? Which approach has the best object-oriented design?
  • Review previous chapters to contextualize how the data structures like ListMapping use the list data structure.

Activities

  • Monday and Wednesday: Hash Tables
    • Explore how to implement hashing functions that map numbers to list indices
    • Investigate trade-offs with bucket size, hashing function, and re-hashing
    • Examine Python source code segments to illustrate key points
  • Thursday: Start new algorithm engineering project
  • Friday: Report on results from algorithm all-hands project

Project

Goal

To build and use a Python program, called lcsfinder, that runs benchmarks to study the performance of finding the longest common sub-sequence of data values

Steps

  • Use lcsfinder as your template repository
  • Install the project’s dependencies using devenv
  • Follow the instructions to complete the project:
    • Week 1: Implement all of the modules in lcsfinder
    • Week 2: Design and conduct experiments and document experimental results
  • Schedule office hours if you have questions

Slides

Full Screen: Week Twelve: Hash Tables

Back to top