A backup client de-duplicates backup data sets using a locally stored, memory resonant, root tag vector and hash cache. To create a new backup data set, the client queries a backup server to determine which of the root hashes in the root tag vector are available on the backup server. If one or more are no longer available, the backup server re-uses a root tag vector entry corresponding to one of the no longer available root hashes. If all are available, the client ages out a root hash for re-use based on a combination of age and represented size. Data is de-duplicated by chunking and hashing it and comparing the resulting hashes to hashes in the hash cache. To prevent the hash cache from growing too large, entries in the hash cache are aged out based on a combination of age and size of data represented by the entries.