Primary clustering

In computer programming, primary clustering is a phenomenon that causes performance degradation in linear-probing hash tables. The phenomenon states that, as elements are added to a linear probing hash table, they have a tendency to cluster together into long runs (i.e., long contiguous regions of the hash table that contain no free slots). If the hash table is at a load factor of ${\displaystyle 1-1/x}$ for some parameter ${\displaystyle x\geq 2}$, then the expected length of the run containing a given element ${\displaystyle u}$ is ${\displaystyle \Theta (x^{2})}$. This causes insertions and negative queries to take expected time ${\displaystyle \Theta (x^{2})}$ in a linear-probing hash table.