Separate Chaining

overview

Remember these Terms

• Hash table: array of buckets for fast key-value lookups.
• Hash function: maps a key to an array index.
• Index: position in the table from the hash.
• Bucket: container for entries sharing one index.
• Collision: two keys map to the same index.
• Separate chaining: put a chain of entries in each bucket.
• Linked list: common chain used to store collisions.
• Load factor: entries divided by buckets; signals when to resize.
• Rehash: recompute indexes after growing the table.