Primary clustering
Phenomenon observed in hash tables / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Primary clustering?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
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 for some parameter
, then the expected length of the run containing a given element
is
. This causes insertions and negative queries to take expected time
in a linear-probing hash table.