The Power of Simple Tabulation Hashing

Details The Power of Simple Tabulation Hashing The Power of Simple Tabulation Hashing

2010-11-23

arxiv.org/abs/1011.5200v2

Computer Science

Data Structures and Algorithms

Scientific paper

Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tables T_1, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_q) is hashed to T_1[x_1] xor ... xor T_c[x_c]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-589452