Multiplicative Hashing

CS2 / C++


  • Kevin Wortman California State University - Fullerton


This is a first introduction to the structure of hash table data structures (array/table, hash function, and buckets). The activity focuses on that conceptual structure, multiplicative hash functions, search and insert operations, and collisions. Implementation details and code are deferred to later activities. The target audience may not have taken a discrete math course, so math concepts (modulo and prime) are reviewed just-in-time, and the inevitability of collisions is invented from concrete evidence and not abstract proof techniques (e.g. combinatorics, 1:1 functions, pigeonhole principle).

This activity was developed with NSF support through IUSE-1626765. You may request access to this activity via the following link: IntroCS-POGIL Activity Writing Program

  • Level: Undergraduate
  • Setting: Classroom
  • Type: Learning Cycle
  • Discipline: Computer Science
  • Course: CS2 / C++
  • Keywords: hash table, collision, chaining, adversarial analysis




How to Cite

Wortman, K. (2023). Multiplicative Hashing: CS2 / C++. POGIL Activity Clearinghouse, 3(4). Retrieved from



CS-POGIL Activity Writing Program