Linear Probing

overview

Remember these Terms

• Hash table: Array storing key-value pairs by index.
• Hash function: Maps a key to an array index.
• Collision: Two keys map to the same index.
• Linear probing: On collision, scan to next free slot.
• Probe sequence: Order of checked slots during probing.
• Load factor: Filled slots divided by table size.
• Clustering: Long runs of filled slots slow searches.
• Tombstone: Deleted marker keeps probe chains intact.
• Resize & rehash: Grow table and recompute indexes.