Key clustering

{{Multiple issues|

}}

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{{cite book | first=Donald |last=Knuth |author1-link=Donald Knuth | title = The Art of Computer Programming | volume = 3: Sorting and Searching | edition = 2nd | publisher = Addison-Wesley | year = 1998 | isbn = 978-0-201-89685-5 | pages = 513–558 }} {{verify source |date=September 2019 |reason=This ref was deleted Special:Diff/902760856 by a bug in VisualEditor and later restored by a bot from the original cite located at Special:Permalink/895004660 cite #3 - verify the cite is accurate and delete this template. User:GreenC bot/Job 18}} is claimed to have particularly poor clustering behaviour.{{Cite web|title = Prime Double Hash Table|url = https://www.concentric.net/~Ttwang/tech/primehash.htm|date = March 1997|accessdate = 2015-05-10|last = Wang|first = Thomas|archiveurl = https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm|archivedate = 1999-09-03}} {{verify source |date=September 2019 |reason=This ref was deleted Special:Diff/902760856 by a bug in VisualEditor and later restored by a bot from the original cite located at Special:Permalink/895004660 cite #9 - verify the cite is accurate and delete this template. User:GreenC bot/Job 18}}

References

Category:Key management