= Linear probing cluster
A maximal consecutive run of occupied or deleted slots in <linear probing>, bounded by never-used slots when any exist; adjacency wraps around by <modular arithmetic>. Deleted slots still belong to the search run.<Open Data Structures: An Introduction by Pat Morin/5.2 LinearHashTable: Linear Probing>[Open Data Structures: An Introduction by Pat Morin; Section 5.2.1, definition of a run using non-nil entries and modular indices]{ref}
In the eight-slot example, <array indices> $0,1,2,3$ form one <linear probing cluster>. Inserting absent <hash table key> $10$ starts at $2$, passes the occupied slots $2,3$, and fills $4$. This extends the same <linear probing cluster> despite $10$ having a different initial <array index> from $0,8,16$. A <hash collision> at the initial slot is enough to make later slots compete too.
For a worst-case family, insert <integer> <hash table keys> $0,m,2m,\ldots,(n-1)m$ into an empty capacity-$m$ <array>, using the <hash function> $h_m(k)=k\bmod m$, where $1\leq n<m$. They occupy <array indices> $0,\ldots,n-1$. Lookup of absent $nm$ needs $n+1$ <hash table probes>. Taking $n=\lfloor m/2\rfloor$ gives <hash table load factor> at most $1/2$ while the number of <hash table probes> grows with $m$. Thus occupancy alone cannot promise constant lookup work.
Before any rebuilding, bounded lookup, deletion by <hash table key>, and insertion with a duplicate check each have worst-case $O(m)$ <time complexity> in <Big O notation>, assuming constant-cost <hash function> evaluation, <array> access and <key equality>. The counterexample gives a matching linear worst-case growth in the number of <hash table probes>. <Hash table resizing> is additional work; expensive <string> comparisons or hashing also fall outside these constant-cost assumptions.
Back to article page
