US Patent 10528539 Optimized selection of hash collision chains

In an example, there is disclosed an apparatus, comprising: a data store comprising 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 one or more logic elements, including at least one hardware logic element, comprising a data compressor to: inspect a string0 comprising n bytes at position p in a data file; get the spill counter from a hash entry corresponding to string0; inspect a string1 comprising n bytes at p+k, wherein k is a positive integer; get the spill counter from a hash entry corresponding to string1; determine that the spill counter for string1 is less than the spill counter for string0; and search 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.