# A hash function with predicted collisions

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$?

• @JeffE I'm not sure about the correct formulation, but I meant function with minimized probability of a collision. – madfriend Aug 6 '12 at 22:26
• I think the word you're looking for is "uniform". – JeffE Aug 7 '12 at 1:16
• 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|$. – Patrick87 Aug 8 '12 at 19:26

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).
• 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? – madfriend Aug 7 '12 at 15:04
• @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)$. – SamM Aug 9 '12 at 4:27