Springe direkt zu Inhalt

Shasha Jiang:

Simple Tabulation Hashing for Chaining


Tabulation Hashing has been regarded as a simple and an effective method to construct universal families of hash functions, which, though three-independent, provides plenty of the algorithmically important probabilistic guarantees that usually higher-independent does.

According to Zobrist, the scheme for simple tabulation hashing is that, we split a key x into c characters: x_1,...,x_c and initialize c totally random tables T_1,...T_c. The hash value comes out by performing exclusive OR operations on the c random codes generated from tables.

This thesis demonstrates why the simple tabulation hashing for chaining has the desired mathematics guarantees, which is the property from truly random hash functions. The proof has been done by Mikkel and Mihai, where the Chernoff bounds and Peeling technique were used.

Bachelor of Science (B.Sc.)