Hash Table
Expected constant-time lookup by mapping keys to buckets
A hash narrows the search
A hash function converts a key into a table index. Good hashing spreads expected keys evenly, so lookup usually examines only a tiny part of the table. Distinct keys can still select the same index; this unavoidable event is a collision.
Separate chaining stores a list per bucket
Chaining keeps colliding entries together. Insertions are simple, deletion is direct once an entry is found, and the table can hold more entries than buckets. Long chains appear when the hash distribution or load factor is poor.
Enter a value and insert it to see which bucket its hash selects.
Open addressing searches the table itself
Linear probing advances through slots until it finds the key or an empty position. It avoids per-entry nodes and has strong cache locality, but dense tables create long clusters. Resizing and rehashing before the load factor becomes too high protects expected O(1) operations.
Insert a value; collisions advance one slot at a time by linear probing.
O(1), but a pathological collision pattern can degrade them to O(n).