1
$\begingroup$

Is there a (weakly) universal hash function for strings without any assumption of the string length?

I did not find one on Google / Wikipedia.

$\endgroup$
1
  • $\begingroup$ What is the range of your hash function? $\endgroup$ May 18, 2021 at 7:29

1 Answer 1

2
$\begingroup$

Any such hash function must have an infinite key.

Suppose that your hash function maps binary strings to some alphabet $\Sigma$ of size $m > 1$. We can identify binary strings with natural numbers, and so can think of the hash function as a function $h\colon K \times \mathbb{N} \to \Sigma$, where $K$ is the (finite) set of keys.

For each $n \in \mathbb{N}$, we can look at the function $h_n\colon K \to \Sigma$ given by $h_n(k) = h(k,n)$. There are finitely many possible functions $h_n$ (at most $m^{|K|}$), and so there must exist $n_1 < n_2$ such that $h_{n_1} = h_{n_2}$. In particular, $\Pr_k[h(k,n_1) = h(k,n_2)] = 1$, and so $h$ is not even a weakly universal function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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