Hashing Universale e High-Speed Hashing: Teoria e Applicazioni

This thesis explores universal hash functions introduced by Carter and Wegman (1979), with particular focus on their applications in hashing integer keys and strings. After providing a theoretical overview of the properties of universal and strongly universal hash families, efficient implementations for 32-bit and 64-bit keys are analyzed, as well as advanced techniques for hashing variable-length and fixed-length strings as summarized by Thorup (2015). The goal is to offer a comprehensive framework of universal hash functions and high-speed hashing techniques, demonstrating their properties from a theoretical perspective and providing examples of real-world applications.

Questa tesi esplora le funzioni di hash universali introdotti da Carter e Wegman(1979), conparti colare attenzione alle loro applicazioni nell’hashing di chiavi intere e stringhe. Dopo aver fornito una panoramica teorica sulle proprietà delle famiglie di hash universali e fortemente universali, si analizzano implementazioni efficienti per chiavi a 32 e 64 bit, nonché tecniche avanzate per l’hashing di stringhe di lunghezza variabile e fissa riassunti in Thorup (2015). L’obiettivo è offrire un quadro completo delle funzioni di hash universali e delle tecniche di hashing ad alta velocità mostrando e dimostrandone le proprietà dal punto di vista teorico, fornendo esempi di applicazioni reali.