Linear hashing is awesome

TY - JOUR

T1 - Linear hashing is awesome

AU - Knudsen, Mathias Bæk Tejs

PY - 2019

Y1 - 2019

N2 - 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].

AB - 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].

KW - Hashing

KW - Hashing with chaining

KW - Linear hashing

UR - http://www.scopus.com/inward/record.url?scp=85065461963&partnerID=8YFLogxK

U2 - 10.1137/17M1126801

DO - 10.1137/17M1126801

M3 - Journal article

AN - SCOPUS:85065461963

SN - 0097-5397

VL - 48

SP - 736

EP - 741

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -