Question

Design a universal hashing scheme using matrix operations.

Answer 1

UNIVERSAL HASHING

• A universal hash function H is set of hash function with following bound on collisions.
• When any hash function h H is chosen randomly from H, the probability of collision of any two keys (key i and key j) is bounded as follows:

The number of collisions of key i with any other key can be bounded.

• Constructing a hash function with this property is not as difficult as it might seem.
  • The crux is having the means to randomize the selection.
• EXAMPLE: Consider a set of functions F.
  • , Where
• F is a class of 100 distinct functions, which vary based on some parameter  
• If we can randomly select i, then we can randomly select function F.

Designing a universal hashing using matrix:

• Assume
  • Keys are u-bits long.
  • Table size m is a power of 2, m=2^b
• Define hash function h in terms of random 0-1 matrix H, that is b x u.
  • 
• EXAMPLE:

M=4 , H    k Hk

keys:3-bits    ​​​​​​​   

Advantage:This is a universal hash ,i.e,

Disadvantage: Hash computation cost: O(log₂  m x log₁ |k|)