Key clustering
From Wikipedia, the free encyclopedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these messages)
(Learn how and when to remove this message)
This article needs additional citations for verification . Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Key clustering" – news · newspapers · books · scholar · JSTOR (November 2019) (Learn how and when to remove this message)
Find sources: "Key clustering" – news · newspapers · books · scholar · JSTOR (November 2019) (Learn how and when to remove this message)
This article may be confusing or unclear to readers. Please help clarify the article. There might be a discussion about this on the talk page. (June 2020) (Learn how and when to remove this message)
Key or hash function should avoid clustering , the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash[1] is claimed to have particularly poor clustering behaviour.[2]
References
[edit ]- ^ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 978-0-201-89685-5. [verification needed ]
- ^ Wang, Thomas (March 1997). "Prime Double Hash Table". Archived from the original on 1999年09月03日. Retrieved 2015年05月10日. [verification needed ]
