1. A method for sub-block partitioning for hash-based deduplication by a processor device in a computing environment, the method comprising: defining a minimal size and maximum size of the sub-blocks; if one of a plurality of search criteria is not satisfied by one of a plurality of hash values, incrementing a current position of one of the plurality of hash values by at least one byte, and if the maximum size of the sub-block is not reached prior to satisfying one of the plurality of search criteria, calculating a next one of the plurality of hash values to test using the one of the plurality of search criteria; if one of the plurality of search criteria is satisfied by one of the plurality of hash values, declaring a position of the one of the plurality of hash values as a boundary position of the sub-block; if the maximum size of the sub-block is reached prior to satisfying one of the plurality of search criteria, declaring a position of an alternative one of the plurality of hash values that is selected based upon an alternative one of the plurality of search criteria as the boundary position of the sub-block; and satisfying one of the plurality of search criteria if n bits at predefined positions of a value calculated by applying an XOR operation on last calculated k hash values are equal to one of an mth predefined different patterns of bits, and applying one of a plurality of operations that combines values of the last calculated k hash values and produces alternative values whose statistical distribution being the same as the statistical distribution of the plurality of hash values being combined.