Re: type of hash functions

Adrian Wong wrote:
I am looking for two hash functions on strings. For different strings
that collide on one hash function it is guaranteed not to collide with
the other hash function. Do such complementary functions exist?

Such a pair of functions can exist, but if the pair does exist, then
the sum of the sizes of the two functions' outputs must be at least
as long as the input string. (Let's assume both keys and input strings
are a fixed size.)

To see why this is so, just think about this: if the pair of functions
exists, then for any string, the pair of keys generated (by the pair
of functions) uniquely identifies the string. Therefore, the original
string can be reconstructed using only the pair of hash keys. And that
means the pair of hash functions can be used as a form of data
compression.

And, it is already well established in the field of compression that
there is no such thing as a data compression function that (a) always
shrinks its input and (b) is lossless (here, being lossless equates
to having no collisions).

Therefore, since the two keys would have to be as big (on average) as
the original input string, even if this pair of functions does exist,
it is probably not that useful.


Note that I'm assuming we are talking about a situation where there
isn't a fixed set of strings to be hashed. If the set of strings is
known in advance, then a hash function can be created that has no
collisions for that set, and the output can be as small as desired
as long as the number of possible outputs is not smaller than the
number of possible inputs (i.e. the output is an integer large
enough to count from 1 to the size of the set of inputs).

- Logan
.

Relevant Pages

  • Re: type of hash functions
    ... key length and possibly infinite string lengths. ... the other hash function. ... exists, then for any string, the pair of keys generated (by the pair ... the original input string, even if this pair of functions does exist, ...
    (comp.programming)
  • Re: type of hash functions
    ... the other hash function. ... but rather reduce the probability that you *need* to as much ... the mere process of storing and comparing hashes not worth the effort. ... pointer to the string) first can help (since many libraries omit this ...
    (comp.programming)
  • Help needed to retrieve text from a text-file using RegEx
    ... I ask user for a input string. ... that input string I retrieve text from a text file. ... I'm just going to help you clean up the loop body. ...
    (comp.lang.python)
  • Re: Nondeterministic turing machines.
    ... Turing Machine (NDTM) is a Turing Machine that has a finite number ... The NDTM is said to accept an input string if, ... there is _some_ sequence of moves such that the NDTM reaches a final ...
    (comp.theory)
  • Re: 32-bit programs on Windows x64
    ... A DFA lexical analyzer does not compare its input string to ...
    (microsoft.public.vc.mfc)
Loading