The load factor of a hash table compares the number of stored keys with the number of slots. In open addressing, a nearly full table gives a lookup fewer empty slots to encounter. With linear probing, nearby collisions can also create clusters. These are related ideas with different definitions.
Draw a collision and follow the probes
Use eight slots numbered zero through seven. Suppose three different keys hash to slot 2. Store the first at 2. The next checks slot 2, then goes to 3. The third checks 2 and 3 before using 4. At that point, the table has load factor 3/8, but the keys occupy one contiguous block. A fourth key that originally hashes to 3 crosses that block to find the next empty slot.
Now draw another eight-slot table with one key each in slots 0, 3 and 6. It has the same load factor. A key that hashes to 3 only checks one occupied slot before finding an empty one. The placement changes the probe path even when the number of entries stays constant.
Contrast the example with a fixed set of keys
Perfect hashing chooses a collision-free arrangement for a known set of keys. A changing key set cannot simply assume that property after arbitrary inserts. When comparing approaches, first ask whether the set is fixed and whether fast updates or quick lookup matter more. Use the same sample keys to compare paths before drawing conclusions about real workloads.
Continue with Oakgen Agent
Open in Oakgen Agent
Review the prefilled prompt before sending.


