Key clustering: Difference between revisions
Content deleted Content added
No1lakersfan (talk | contribs) |
GreenC bot (talk | contribs) Restore 2 cites deleted by a bug in VisualEditor (vebug bot) |
||
| Line 4: | Line 4: | ||
}} |
}} |
||
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< |
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> |
||
[[Category:Key management]] |
[[Category:Key management]] |
||
Revision as of 17:12, 4 September 2019
 | 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]
 | This cryptography-related article is a stub. You can help Wikipedia by expanding it. |
- ^ 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]