Patent ID: 8156126

Claim:
A method of allocating data on physical media by a file system that eliminates duplicate data, comprising the steps of: providing user data stored on a storage device; inputting the user data into a hash algorithm to create a hash value output having a hash bit length; distributing the hash value output across an entire range of an output digest; creating a static array of elements that has a length of 2 N with N<D, where N is the first partial bits of a hash value output and D is the number of bits in the hash value output; creating a dynamic search node array having at least one search node therein; pointing each element in the static array to a corresponding at least one search node; creating an integer index I and a primary cache hint of a length 2 H in the at least one search node where the size of a search node element equals (I)+H with H being the next portion of bits to be compared; the integer index containing an address in persistent storage of a computer; storing a full hash value and reference count in the address; searching the first N bits of a hash value output in the static array for a match therewith; if no matches are found, inserting a new search node in the dynamic search array and referenced by its respective address; if a match is found, inspecting each search node in the dynamic array for a matches with a secondary cache hint consisting of the next H bits of the hash value; searching for match with the entire hash value if there is a match with the secondary cache hint.