Optimized selection of hash collision chains

A method of providing a data compressor, comprising:

• providing a hash table having for at least some rows a hash entry indexed by a hash value, and comprising a hash chain of one or more pointers to a history buffer, and a spill counter;
• and
• inspecting a string0 comprising n bytes at position p in a data file;
• getting the spill counter from a hash entry corresponding to string0;
• inspecting a string1 comprising n bytes at p+k, wherein k is a positive integer;
• getting the spill counter from a hash entry corresponding to string1;
• determining that the spill counter for string1 is less than the spill counter for string0;
• and
• searching a chain1 (the hash chain of a hash entry corresponding to string1) for a matching string of size at least n+k with an offset of −k.

One or more tangible, non-transitory computer-readable mediums having stored thereon executable instructions for:

• providing a hash table having for at least some rows a hash entry indexed by a hash value, and comprising a hash chain of one or more pointers to a history buffer, and a spill counter;
• and
• inspecting a string0 comprising n bytes at position p in a data file;
• getting the spill counter from a hash entry corresponding to string0;
• inspecting a string1 comprising n bytes at p+k, wherein k is a positive integer;
• getting the spill counter from a hash entry corresponding to string1;
• determining that the spill counter for string1 is less than the spill counter for string0;
• and
• searching a chain1 (the hash chain of a hash entry corresponding to string1) for a matching string of size at least n+k with an offset of −k.