Covers hash compression concepts including modular arithmetic, prime number table sizing, and folding techniques (shift and boundary), serving as the navigational outline that guides learners through the sequence of topics in the module.
Module Artifacts — 6 items
This reading introduces hash functions and hash compression, explaining how keys are converted into numeric table indices and why this process is fundamental to data structures like hash tables used in everyday applications such as phone contacts and compilers.
This reading explains how modular arithmetic (the division method) is used as a compression strategy to map arbitrary keys into valid hash table indices, covering its mechanics, advantages, and practical considerations for achieving efficient average-case performance.
This reading covers folding and other compression techniques—such as digit folding and shift folding—that break large keys like social security numbers or product codes into smaller parts and combine them to produce a hash table index within a manageable range.
This reading examines the distribution properties of hash functions, explaining what uniform distribution means, why it matters for minimizing collisions, and how to evaluate whether a hash function spreads keys evenly across a table's available slots.
This reading compares multiple hash compression methods—such as modular, MAD, and bit-masking approaches—discussing their trade-offs in terms of distribution quality, computational cost, and suitability for different data types to guide method selection.
This reading compares multiple hash compression methods—such as modular, MAD, and bit-masking approaches—discussing their trade-offs in terms of distribution quality, computational cost, and suitability for different data types to guide method selection.