5
$\begingroup$

As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides for some known set of possible inputs and avoids collisions for other input values. To state the problem simpler:

Let $A$ be some set of strings. Define a function $f$ such that $f(x_i) \rightarrow y_i$ with $y_i \neq y_j$ for all $i,j \notin A$ with $i \neq j$, and otherwise $f(x_i) \rightarrow y$ where $y \notin \{y_i \mid i \notin A\}$ is constant.

Is it possible? In addition, is it possible for performance of such a hash function not to depend on the size of $A$?

Improve this question
$\endgroup$
3
  • $\begingroup$ @JeffE I'm not sure about the correct formulation, but I meant function with minimized probability of a collision. $\endgroup$
    – madfriend
    Aug 6, 2012 at 22:26
  • $\begingroup$ I think the word you're looking for is "uniform". $\endgroup$
    – JeffE
    Aug 7, 2012 at 1:16
  • 1
    $\begingroup$ I'd say that it has to depend on $|A|$. I won't try to formalize this in an answer (for a variety of reasons, not least among which is that I don't know whether this argument makes any sense), but here it is. If $A$ is finite, then any membership check must check for string length (explicitly or accidentally) to exclude arbitrarily large strings. The length of the longest string in $A$ is bounded below by an expression involving $|A|$ and $|\Sigma|$, the size of the alphabet. So any condition(s) that, when checked, result in a finite $A$, must take time depending on $|A|$. $\endgroup$
    – Patrick87
    Aug 8, 2012 at 19:26

1 Answer 1

Reset to default
5
$\begingroup$

Generally the collisions in a hash function are, in a way, what winds up improving the running time.

This is because running time (or size, or insertion time) is generally defined in terms of worst-case input. If you use an algorithm without any randomness or hash, you need to deal with the worst case. For example, finding duplicate elements in an array has an $\Omega(n\log n)$ in the comparison model, same as sorting. But if you just hash the values, you can determine whether or not there's a duplicate in $O(n)$ time and space with a small probability of error. Determining a hash function that wouldn't collide, eliminating the possibility of error, has to take $\Omega(n\log n)$ time. (You may notice that these are, in a way, the same problem--though of course hashed values generally belong to a smaller universe and the comparison model may not be appropriate).

That said, there are some ways to take advantage of the ways hash functions collide. One is locally sensitive hash functions, in which elements with small differences (i.e. normal distance functions for points) hash to the same value. Recently I've been reading this paper(1), which I found really easy to read, and shows some good, intuitive applications for how a locally sensitive hash function can be used to solve seemingly difficult problems--in this case the nearest neighbor problem with small probability of error.

Incidentally, the space advantage of possible collisions is how bloom filters work, a data structure that allows you to store elements of a set, each in space smaller than their actual size. They are a constant factor away from optimal, and the upper and lower bounds demonstrate the tradeoff between error and space.

(1) Neylon, T. A locally sensitive hash for real vectors. SODA2010.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By the way. As far as I know, bloom filters still take $O(n)$ time, because the worst case is just a basic lookup. Is there way to speed things up? $\endgroup$
    – madfriend
    Aug 7, 2012 at 15:04
  • $\begingroup$ @madfriend examples for what? Bloom filters take $O(n)$ space and $O(k)$ time, where $k$ is the number of hash functions. (This is slightly incorrect as it takes $k$ hashes, which are generally $w^{O(1)}$ where $w$ is the word size). $k$ has nothing to do with $n$ and certainly should not be $O(n)$. $\endgroup$
    – SamM
    Aug 9, 2012 at 4:27

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.