Independence of Tabulation-Based Hash Classes

Details Independence of Tabulation-Based Hash Classes Independence of Tabulation-Based Hash Classes

2011-12-14

arxiv.org/abs/1112.3323v1

Computer Science

Data Structures and Algorithms

12 pages with 2 page appendix showing experimental results

Scientific paper

A tabulation-based hash function maps a key into d derived characters indexing random values in tables that are then combined with bitwise xor operations to give the hash. Thorup and Zhang (2004) presented d-wise independent tabulation-based hash classes that use linear maps over finite fields to map a key, considered as a vector (a,b), to derived characters. We show that a variant where the derived characters are a+b*i for i=0,..., q-1 (using integer arithmetic) yielding (2d-1)-wise independence. Our analysis is based on an algebraic property that characterizes k-wise independence of tabulation-based hashing schemes, and combines this characterization with a geometric argument. We also prove a non-trivial lower bound on the number of derived characters necessary for k-wise independence with our and related hash classes.

Affiliated with

Also associated with

No associations

Rating

Independence of Tabulation-Based Hash Classes 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 Independence of Tabulation-Based Hash Classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independence of Tabulation-Based Hash Classes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-560920