Key clustering

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. 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. https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm. Retrieved 2015-05-10. ^{[verification needed]}

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Key clustering. Read more

[1] Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 978-0-201-89685-5. ^{[verification needed]}

[2] Wang, Thomas (March 1997). "Prime Double Hash Table". Archived from the original on 1999-09-03. https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm. Retrieved 2015-05-10. ^{[verification needed]}

[1]

[2]

Key clustering

Topic: Social

References