Key clustering: Difference between revisions
Content deleted Content added
No edit summary |
fixed maint tag |
||
| Line 2: | Line 2: | ||
{{Refimprove|date=November 2019}} |
{{Refimprove|date=November 2019}} |
||
{{Confusing|date=June 2020}} |
{{Confusing|date=June 2020}} |
||
}} |
|||
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 bot/Job 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 bot/Job 18]]}}</ref> |
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 bot/Job 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 bot/Job 18]]}}</ref> |
||
Revision as of 02:40, 6 January 2021
 | 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)
|
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
- ^ 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]
 | This cryptography-related article is a stub. You can help Wikipedia by expanding it. |