Key clustering: Difference between revisions

Revision as of 17:12, 4 September 2019

Revision as of 05:13, 2 November 2019

Line 1:

{{Multiple issues|

{{UnreferencedRefimprove|date=JulyNovember 20172019}}

{{Underlinked|date=June 2019}}

}}

Key or hash function should avoid ''[[Hash table|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<ref>{{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_botGreenC bot/Job_18Job 18]]}}</ref> is claimed to have particularly poor clustering behaviour.<ref>{{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_botGreenC bot/Job_18Job 18]]}}</ref>

==References==

{{Reflist}}

[[Category:Key management]]