Strongly universal string hashing is fast

Details Strongly universal string hashing is fast Strongly universal string hashing is fast

2012-02-22

arxiv.org/abs/1202.4961v1

Computer Science

Databases

Software is available at http://code.google.com/p/variablelengthstringhashing/

Scientific paper

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 requires 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-powered processors. Our tests include hash functions designed for processors with the Carry-Less Multiplication (CLMUL) instruction set. We also prove, using accessible proofs, the strong universality of our families.

Affiliated with

Also associated with

No associations

Rating

Strongly universal string hashing is fast does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Strongly universal string hashing is fast, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strongly universal string hashing is fast will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-415572