Linear hashing is awesome

Research output: Contribution to journalJournal articleResearchpeer-review

Mathias Bæk Tejs Knudsen

We consider the hash function h(x) = ((ax + b) mod p) mod n where a, b are chosen uniformly at random from { 0, 1, . . ., p - 1} . We prove that when we use h(x) in hashing with chaining to insert n elements into a table of size n the expected length of the longest chain is Õ ( n 1 / 3) . The proof also generalizes to give the same bound when we use the multiply-shift hash function by Dietzfelbinger et al. [J. Algorithms, 25 (1997), pp. 19-51].

Original languageEnglish
JournalSIAM Journal on Computing
Volume48
Issue number2
Pages (from-to)736-741
Number of pages6
ISSN0097-5397
DOIs
Publication statusPublished - 2019

    Research areas

  • Hashing, Hashing with chaining, Linear hashing

ID: 223570742