Definition: The tendency for entries in a hash table using open addressing to be stored together, even when the table has ample empty space to spread them out.
See also primary clustering, secondary clustering, k-clustering, clustering free.
Note: In machine learning, "clustering" means to group together objects that are similar, usually to determine meaningful classes or concepts. After Keith Cassell, 29 Dec 2005.
Clustering leads to inefficiency because the chances are higher that the place you want to put an item is already filled. The effect is like having a high load factor in the areas with clustering, even though the overall load factor may be quite low.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 30 December 2005.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "clustering", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 30 December 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/clustering.html