Strongly universal string hashing is fast [r-libre/194]

Lemire, Daniel et Kaser, Owen (2014). Strongly universal string hashing is fast. Computer Journal, 57 (11), 1624-1638. https://doi.org/10.1093/comjnl/bxt070

Fichier(s) associé(s) à ce document :

PDF - 1202.4961v5.pdf
Licence : Creative Commons CC BY-NC.

Télécharger

Catégorie de document :	Articles de revues
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families—though they require a large buffer of random numbers—are often faster than popular hash functions with weaker theoretical guarantees. Moreover, conventional wisdom is that hash functions with fewer multiplications are faster. Yet we find that they may fail to be faster due to operation pipelining. We present experimental results on several processors including low-power processors. Our tests include hash functions designed for processors with the carry-less multiplication instruction set. We also prove, using accessible proofs, the strong universality of our families.
Adresse de la version officielle :	http://comjnl.oxfordjournals.org/content/early/201...
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	14 juill. 2014 20:13
Dernière modification :	16 juill. 2015 00:46

Actions (connexion requise)

RÉVISER