Geek asks and answers

Composite hash of ordered list

Suppose I have an ordered list of n objects (x1, x2, ..., xn) of some type (for example, binary data files of variable length).

Each of these objects was protected by hashing (e.g. SHA1) to create an x-bit hash code (h1, h2, ..., hn)

Now I want to combine these hash codes into a composite code that uniquely and reliably (ignoring the likelihood of an accidental collision) identifies an ordered list.

(Assume the objects are large and reading their actual data is again not an option)

One naive and wrong way to do this would be XOR hash codes together. This has the undesirable property that (x1, x2) will have the same composite code as (x2, x1).

By what algorithm can I combine hash codes with the desired properties?

+3
source share
2 answers

For consistency and security reasons, I would combine the individual hashes of the list items by applying SHA-1 to the concatenations of the SHA-1 hashes of individuals.

+2
source

Perhaps you can use the same algorithm as in java for list hashes, this is an example for a 32-bit hash code

int hashCode = 0;
for(Element e:list) {
   hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
}

For layering you can use another prime number. I hope you get the basic idea of ​​this algorithm and can apply it to arbitrary x-bit hash codes.

+1
source

More articles:


All Articles