A computer implemented method, comprising: receiving a data stream having a plurality of data zones (206, 302), wherein each zone includes a zone identifier; generating a plurality of hashing values for each zone in the plurality of zones, wherein each hashing value in the plurality of hashing values is generated using a portion of a zone in the plurality of zones; generating a storage structure (1500, 1600) having a plurality of storage containers, each storage container in the plurality of storage containers stores one or more hashing values in the plurality of hashing values associated with each respective storage container and a plurality of zone identifiers referencing the associated one or more hashing values, wherein at least one storage container stores a listing of zone identifiers stored in each storage container in the plurality of storage containers; deduplicating, using the storage structure, the received data stream; and inserting a new zone identifier and a new corresponding hashing value referencing the new zone identifier, the inserting includes determining whether the new corresponding hashing value is stored in one or more storage containers in the plurality of storage containers; wherein upon determination that the new corresponding hashing value is not stored in the one or more storage containers, the new zone identifier and the new corresponding hashing value are encoded using a number of storage containers and stored in at least one storage container; upon determination that the new corresponding hashing value is stored in the one or more storage containers, the new zone identifier is encoded using the number of storage containers and stored in the storage container storing the new corresponding hashing value. receiving a data stream having a plurality of data zones (206, 302), wherein each zone includes a zone identifier; generating a plurality of hashing values for each zone in the plurality of zones, wherein each hashing value in the plurality of hashing values is generated using a portion of a zone in the plurality of zones; generating a storage structure (1500, 1600) having a plurality of storage containers, each storage container in the plurality of storage containers stores one or more hashing values in the plurality of hashing values associated with each respective storage container and a plurality of zone identifiers referencing the associated one or more hashing values, wherein at least one storage container stores a listing of zone identifiers stored in each storage container in the plurality of storage containers; deduplicating, using the storage structure, the received data stream; and inserting a new zone identifier and a new corresponding hashing value referencing the new zone identifier, the inserting includes determining whether the new corresponding hashing value is stored in one or more storage containers in the plurality of storage containers; wherein upon determination that the new corresponding hashing value is not stored in the one or more storage containers, the new zone identifier and the new corresponding hashing value are encoded using a number of storage containers and stored in at least one storage container; upon determination that the new corresponding hashing value is stored in the one or more storage containers, the new zone identifier is encoded using the number of storage containers and stored in the storage container storing the new corresponding hashing value. upon determination that the new corresponding hashing value is not stored in the one or more storage containers, the new zone identifier and the new corresponding hashing value are encoded using a number of storage containers and stored in at least one storage container; upon determination that the new corresponding hashing value is stored in the one or more storage containers, the new zone identifier is encoded using the number of storage containers and stored in the storage container storing the new corresponding hashing value.