Is there a (Well known) hash function for string s which can be computed from hashes of subsets of s. e.g.
hash(0 to x) is hash(0 to x/2) + hash(x/2 to x) // plus or any other mathematical operation
A:
A plain checksum (modulo some value) fits this description, but in many instances it would be considered a rather poor hash with regards to various characteristics of a hash function. For example such a hash can easily be "broken" (if used in the some cryptographic scheme) and also it produces the same value for similar input, where the order of of a few characters in the input is changed.
mjv
2010-01-03 23:48:03
+1
A:
I don't think there is such a "hash" function. Of course mathematical functions will exist... but the purpose of a hash function is to make the hash as little dependant on the entry so that the hash will be as random as possible.
If you think about it, your hash function would be flawed from the begining ... after all I could compute:
Hash("password") = Hash("pass") + Hash("word")
then
Hash("word") = Hash("wo") + Hash("rd")
and so on.... so finally recursively building will equal recursively constructing ... which is bad for a hash function.
Jorge Córdoba
2010-01-03 23:49:13
this assumes that he wants a cryptographic hash that depends on security. There are plenty of uses for hashes that doesn't necessarily depend on security, e.g. for fast random database retrieval (e.g. a fast way of finding similar records using hashes as a heuristic). see applications of hash functions http://en.wikipedia.org/wiki/Hash_function#Applications
Charles Ma
2010-01-04 00:01:57
+5
A:
You can construct a hash tree with any hashing function you like. So if you just need a custom hash function for your application that can be calculated from parts of data, you can build it from any well known hashing function.
A fairly commonly used variant of hash trees would be Tiger Tree Hashes, which use the Tiger algorithm.
sth
2010-01-03 23:56:01
+1 That would be both "secure" and recursive... Summarizing the "+" in the function shall be a one-way mathematical function.
Jorge Córdoba
2010-01-03 23:59:19
I have been working on Tiger for some time now, its sort of hard to make such a hash, any suggestions, idea?
hasanatkazmi
2010-02-12 21:21:01
A:
There are many hash functions solving for your problem. In my opinion the best, and suitable for the most applications is something similar to what is defined here:
http://en.wikipedia.org/wiki/Rolling_hash#Rabin-Karp_rolling_hash
It is important to pick some good and big constants for the implementation. You need to do some math (modular arithmetic) to implement the concatenation in O(1) (to get H(AB) from H(A) and H(B)). You can also do the opposite (e.g. compute H(A) from H(AB) and H(B))
Milo
2010-09-04 22:12:32