I don't see the point of using hashes. Using hashes means that at least one extra read will be done on the target to compute the candidate target hash. It's bad for a cloud provider where IOs count is a huge cost.
Another structure to replace a bitmap (smaller on the canonical case) would be a block table as described in the Hystor paper: www.cse.ohio-state.edu/~fchen/paper/papers/ics11.pdf Best regards Benoît
