= Primary clustering
In an insertion-only table, an absent <hash table key> starting anywhere inside a <linear probing cluster> reaches its far end. Filling a one-slot gap can merge two runs, joining <hash table keys> with different initial <array indices> into one long search route. The insertion of $10$ above exhibits this effect without a <hash collision> with $0$ at their initial slots.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 10: Hashing III: Open Addressing>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; Lecture 10: Hashing III: Open Addressing, pp. 3–4, Linear Probing and Figure 4: Primary Clustering]{ref}
Back to article page
