1
$\begingroup$

Given Hashtable $T[0,..,m-1]$ and $U = \{0, . . . , n − 1 \}$ set of possible keys $k$ with $m \ll n$

Let $$h: U \rightarrow \{0, . . . , m − 1 \} $$

I am trying to understand why the hash functions $$h_{1}(k) =\Big\lfloor m\Big(\frac{k}{n}\Big)^2 \Big\rfloor$$ and

$$h_{2}(k) =\Big(l \Big\lfloor \frac{m}{n} k \Big\rfloor\Big) \text{mod } m \qquad l \in \mathbb{N}$$

would be considered a bad choice. I understand that a good hash function should have higher probability to be injective (Correct?) but I still can't see how this applies in these specific cases based on the functions formula.

I've tried different values for $h_1$ and $h_2$ and it's obvious that when $k_1$ and $k_2$ are close then $h(k_1) = h(k_2)$ Is there a way to formally prove this?

Help?

$\endgroup$
0
$\begingroup$

At least in computer science, a good hash function has as little as possible collisions (it makes the algorithm faster) -a collision happens when we have $k_{1} \neq k_{2}$ with the same hash value, $h(k_{1}) = h(k_{2})$. When a hash function is injective, it is called "perfect hash function"-it has no collisions. So, as you said, a good hash function should have higher probability to be injective. However, notice that with your condition $m<<n$, we cannot have $h:U\rightarrow \{0, 1, 2, ..., m-1\}$ injective, since the cardinality of $U$ $(|U|=n)$ is greater than the cardinality of $T$ $(|T|=m)$.

Looking to your hash function $h_{1}$, it seems that when $k$ and $m$ are too small compared to $n$, there will be many $k\in U$ such that $h_{1}(k) = 0$. For exemple, if $n=2^{m}$, $h_{1}(k)= 0$ for every $k < \frac{2^{m}} {\sqrt{m}}$. I think it would be better if you use just $$ h(k) = m \left\lfloor\dfrac{k}{n}\right\rfloor $$ This way you know you are distribuiting your values with the same quantity of collisions, what is good - unless you know beforehand what values you are going to use more. In fact, if you are going to use only a part $G\subset U$, you can look for a injective function (if $|G| \leq m$, of course). That is the best scenario for hash functions: when you have $\alpha \leq m$ numbers and you know who they are.

Your hash function $h_{2}$ looks fine, although you must choose a convenient $l$ - for example, if $l=pm, p\in \mathbb{N}$, $h_{2}(k) = 0\ \forall k\in U$.

About this "I've tried different values for h1 and h2 and it's obvious that when $k_{1}$ and $k_{2}$ are close then h(k1)=h(k2) Is there a way to formally prove this?": we can have $k_{1}$ and $k_{2}$ "really" close $(k_{2}=k_{1}+1)$ and $h_{2}(k_{1})$ completely different from $h_{2}(k_{2})$. However, $$ \left\lfloor\dfrac{mk_{1}}{n}\right\rfloor = \left\lfloor\dfrac{mk_{2}}{n}\right\rfloor \Rightarrow h_{2}(k_{1}) = h_{2}(k_{2}) $$

Perhaps a better choice for your hash function would be just $h(k)=(lk)$ mod $m$, where $l$ is preferably a prime number -and big enough so we don't have many $k$ such that $h(k)=0$. This way, even if $k_{1}$ and $k_{2}$ are close to each other, they are not likely to have the same hash value (and it is convenient for security reasons).

I said that if you know what values from $U$ you are going to use, you can search for a perfect hash function, but it is frequently done by brute force algorithms.

If you don't mind, I would like to recommend you this book, Open Data Structures, from Pat Morin.

$\endgroup$
0
$\begingroup$

This is not a math question, but a computer science question.

There is no intrinsic problem if a hash functions gives collisions for similar keys — the problem is that when programs tend to work with many similar keys and put them in the hash table, they'll see poor performance.

This is a common use case, which is why such a hash function is considered to be bad. But for the occasional program that only uses dissimilar keys can use such a hash function just fine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.