2
$\begingroup$

When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like the family doesn't exists and we only have this one function.

Therefore, the only logical thing seems to be switching a hash function every once in a while (picking a new function from our family). If indeed this is what we should do, how often should we switch functions? How should this time period be selected and is there an optimal time period for different tasks?

Also, suppose we have two hash functions $h_1, h_2$, and then store values in an array according to $h_1$. After a while, we switch our has function to be $h_2$. Do we have to re-hash all of our values according to $h_2$? This seems rather wasteful

$\endgroup$
2
  • 2
    $\begingroup$ I think you need to clarify the applications of hash families here. Are you interested in proving theoretical bounds, or are you talking about use in computer programs? $\endgroup$
    – Pål GD
    May 1, 2021 at 10:56
  • $\begingroup$ @PålGD I refer to use in actual programs, because when proving things (for example "if $h$ is a function in the universal family and a key $k$ is in our table, then the search time complexity for $k$ is $\alpha$, which is the load factor) we simply use the fact that $H$ is universal if $\forall k_1 \neq k_2$ the number of functions $h\in H$ with $h(k_1)=h(k_2)$ is at most $\frac{|H|}{m}$ where $m$ is the size of our hash-table. But in practice, if we use only one function $h$ without switching it, its effectively like the rest of the family doesn't exist. $\endgroup$ May 1, 2021 at 12:08

1 Answer 1

2
$\begingroup$

You need to decide what sort of resilience you are expecting from your hash function. While it is true that once picked, your hash function does not change (and in a sense "the rest of the family doesn't exist") but you're ignoring the crucial part of picking the function at random.

Suppose that $\mathcal{H}\subseteq U^{[m]}$ is a universal family, $h$ is chosen uniformly at random from $\mathcal{H}$, and is subsequently used to hash elements from $U$ into $m$ cells via chaining. This guarantees that regardless of what is the current content of the table, if the load factor is $\alpha=n/m$, then for every $x\in U$ (note the worst case analysis, as opposed to the average case analysis in the simple uniform hashing case) the expected search/insertion time for $x$ is $O(\alpha)$, where the expectation is taken over the initial choice of $h$ (this is the only place where randomness occurs). This remains true regardless of how many operations were done since the initialization, the random choice of $h$ guarantees low expected search time for all inputs.

Switching might come to mind if you are looking for robustness against certain types of adversaries. If the entire problem was handling a user giving you inputs and hashing them to a table, then everything's fine. This changes if you are looking at the problem of an adversarial user with more access, say e.g. that he might learn the hash value of some elements (which happens in real world attacks based on response time analysis). In that case, the adversarial user might be able to recover $h$ and then send you tailored inputs that will cause high search time. This relied on the adversary having a richer interface than just being able to send arbitrary values (which alone, as we saw above, can't cause problems). Now you're entering the world of cryptographically secure hash functions, and here some switching mechanism might be of use. This requires an entirely different formalization, and to say something interesting about parameters such as switching intervals we need to be clear about what sort of robustness we want to achieve.

$\endgroup$

Your Answer

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

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