Method for the allocation of data on physical media by a file system that eliminates duplicate data

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 2N 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 2H 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.