This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy because they give you a small (and fixed-sized) hash code for any file, which can be later used to efficiently determine if that file is different from another file, and (if we are willing to ignore the unlikely possibility of hash-collisions) also whether two files are the same.

One small downside to computing the hash/fingerprint for a file is that you have to read the entire file in order to do so; if the file is very large (e.g. gigabytes or more) this can be an expensive operation.

A good way to avoid that expense is to compute the file's hash code as you are writing it to the disk, and store the hash code with the file. You can even resume updating the hash code later on, if/when you append more bytes to the end of the file, and (assuming no bugs or filesystem corruption) you'll have the file's fingerprint/hash cheaply available to you at all times.

However, the above "update as you go" approach seems like it may break down if you want to update the file in other ways besides appending -- in particular, if you want to truncate the file, or overwrite some existing bytes within the file with new values, you might have to then re-read the entire file in order to update the fingerprint/hash to the appropriate new value.

My question is, is there a type of hashing/fingerprinting algorithm that can efficiently handle file-truncation and byte-overwrite operations, and still provides reasonably good-quality hashing/fingerprinting? ("efficiently" in this case means that one could perform one of these operations on the file and then compute the correct new hash/fingerprint without having to re-read other parts of the file)


One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm.

Let the file be partitioned in blocks of fixed size, $H$ be a hash-function, and $h_t$ be a value stored in a node $t$. If $t$ is a leave, then $h_t$ is a hash of the corresponding block. If $r$ is a parent of $a$ and $b$, then $h_r = H[(h_a,h_b)]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.