Multiplicative Hashing

CS2 / C++

Abstract

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