Skip to content
Ameen Abozaid
Englishالعربية
BEG-041

Hashing

  • 5 Lessons
  • 55 min of reading
  • 3 h practice (estimate)
Start module
On this page 8 topics

Overview

Topics

  • Hash functions
  • hash tables
  • collisions
  • hash-based collections

Learn first

55 min of reading · 3 h of practice (estimate)

Learning outcomes

  1. Explain how a hash table maps keys to buckets.
  2. Describe collision handling (chaining, open addressing) and load-factor resizing.
  3. Explain why a bad hashCode degrades HashMap performance and why mutable keys break it.

Lessons

  1. 01Hash functions11 min read
  2. 02Hash tables and buckets10 min read
  3. 03Collisions and resizing12 min read
  4. 04Inside HashMap and HashSet11 min read
  5. 05Demo: MyHashMap and the constant-hashCode slowdown11 min read

Lab and exercises

Lab

BEG-041-LAB1 · MyHashMap

Outcomes: 1–3 · Time: ~3 h

  1. Implement a chaining-based MyHashMap<K,V> with put, get, remove, size, and load-factor resizing.
  2. Test it, including replacing an existing key and a missing key.
  3. Create a key class with a constant hashCode; time 20,000 inserts and lookups with it and with a good hashCode; record both timings.

Acceptance: tests pass; timing evidence.

Exercises (assessment: implementation plus quiz)

IDOutcomeTask
BEG-041-EX011With 5 buckets and index = hash % 5, place keys with hashes 12, 7, 22, 3, 17 and say where the collisions are.
BEG-041-EX021Explain in three sentences how get finds a value without scanning the whole table.
BEG-041-EX032Compare chaining and open addressing in two sentences each.
BEG-041-EX042A table has 16 buckets and load factor 0.75. At which entry count does it resize, and to what size?
BEG-041-EX053A Point class overrides equals but not hashCode. Describe what goes wrong when you put it in a HashSet.
BEG-041-EX063A key is stored in a HashMap, then one of its fields changes. What happens to get(key), and how do you avoid it?
Show solutions
  • EX01 Indexes: 12 -> 2, 7 -> 2, 22 -> 2, 3 -> 3, 17 -> 2. Keys 12, 7, 22, 17 collide in bucket 2; 3 is alone in bucket 3.
  • EX02 get computes the key's hash, turns it into a bucket index, and opens only that bucket. It compares keys with equals along the short chain there. The rest of the table is never touched.
  • EX03 Chaining: each bucket holds a list of entries, and colliding keys are added to it; easy to implement. Open addressing: all entries live in the array itself, and a collision probes for the next free slot; saves node objects but needs care when removing.
  • EX04 Resize when entries exceed 12 (16 x 0.75); new capacity 32.
  • EX05 Two equal points can have different hash codes, so they land in different buckets and the set may hold duplicates or fail contains. Always override both methods together.
  • EX06 The hash changes, so get looks in a different bucket and returns null (the entry is still inside, unreachable). Use immutable keys such as String, Integer, or records.

Quiz

Outcomes: O1 hash tables and buckets · O2 collisions and resizing · O3 bad hash codes and mutable keys.

A self-check for you: nothing is graded, saved or sent anywhere. Choose an answer, then check it. You can try again as often as you like.

  1. 1A hash function turns a key into:O1
  2. 2If a.equals(b) is true, their hashCode() values must be:O1
  3. 3In a hash table, the bucket for a key is chosen from:O1
  4. 4Average cost of HashMap.get:O1
  5. 5Two different keys in the same bucket is called a:O2
  6. 6Chaining handles collisions by:O2
  7. 7Load factor is:O2
  8. 8When the load factor limit is passed, the table:O2
  9. 9A hashCode that always returns the same number makes lookups about:O3
  10. 10Changing a key after putting it in a HashMap can cause:O3

Practical part

Implementation of MyHashMap (lab BEG-041-LAB1) with timing evidence, plus this quiz and exercises BEG-041-EX01 to EX06. Pass: tests pass, timing shows the constant-hash slowdown, and at least 8 of 10 quiz answers correct.

Common mistakes

Mutating a key after insertion; assuming HashMap iteration order.

Assessment

Implementation plus quiz.

Career relevance

Caching (MID-037), partitioning (MID-028), sharding (SRC-007).

Type to search levels, phases, modules and lessons.