# Universal hashing family

I'm not really sure this question is proper for MathExchange but I have found it more suitable than StackOverFlow.

So, I'm taking the course of Data Structures and Algorithms and we got some example for a hashing function family described by a matrix.

I also found it be taught by MIT through this lesson: https://www.youtube.com/watch?v=z0lJ2k0sl1g&t=3424s

And I have some questions regarding this example as shown during 32:00 to 36:30:

1. I begun losing him in 33:24 when he suggests to represent every key by the base of $$m$$ and this key is somehow translated to a vector of $$m$$ coordinates, and the process of transforming it to a vector is not really understandable.

2. Then he takes some key, representing it by a column vector, defining a dot product which generates hashes to other keys (?).

So, these two points are pretty not clear for me, and I also tried to think of a suitable matrix for this kind of hash function couldn't find one.

Can someone clarify these issues?

• Could you please make the post more self-contained by adding the main content of the relevant part of the video? – Berci Jun 7 at 14:27
• @Berci It will probably just complicate the issue than it is really. – HelpMe Jun 7 at 15:18

Let's start with a simplified "universe" (his term, not mine), the integers from $$0$$ to $$63$$. There are $$64$$ total elements in this universe, and we see that $$64 = 2^6$$. In other words, for every key in our universe, I can represent it as a vector in base-$$2$$ with six coordinates. For example, $$42$$ can be represented as $$(1, 0, 1, 0, 1, 0)$$, and $$13$$ can be represented as $$(0,0,1,0,1,1)$$. Here I'm taking the leftmost entry to be the most significant digit. These representations look awfully familiar: concatenate the entries, and you have the binary representation of a number: $$42_d = 101010_b$$, $$13_d = 001011_b$$, etc.
Take a moment to remember our ultimate goal in creating a hashing function: we want to map any key to an integer between $$0$$ and the number of "buckets," $$m$$. He defines the hash function as follows: take the dot product of some randomly pre-chosen key $$a$$ and the key $$k$$ which you wish to hash, then take the result modulo $$m$$ (this is to ensure that the hash function returns a number between $$0$$ and $$m$$, inclusive). So if I'm trying to hash $$13$$ and my pre-chosen key $$a$$ was $$42$$, then I would first compute the dot product of their vector representations: $$(1,0,1,0,1,0) \cdot (0,0,1,0,1,1) = 2$$, then take the remainder when divided by $$m$$ ($$m$$ = 2 in this example, so our hash function returns $$0 \equiv 2 \text{ mod } 2$$).
• In this example, $m=2.$ – saulspatz Jun 7 at 14:54
• Okay. So it becomes clear. But I'm not sure about that chosen $a$. Do we actually generate our hash function out of some random key? Why is it? And can we generate a matrix which represent this hash function? Will this matrix be linear at all? Generally, now the creating of the hash function is pretty vague for me. Thank you for this good answer! – HelpMe Jun 7 at 15:16
• Yes, I think for the purpose of his lecture, it was random. For example, I could just choose arbitrarily, as in the example, that $a=42$. I don't think there's really a difference so long as you don't choose $a = 0$, but for simplicity, he just chose it to be random. – paulinho Jun 7 at 15:37
• As for the question about matrices, I guess you could define the matrix $B = a^T$ over the finite field $\mathbb{F}_m$, and premultiply any key $k$ that you wish to hash by $B$, i.e. hash($k$)=$Bk$. – paulinho Jun 7 at 15:39