The linked list is crucial to the patent, as the "external chaining" way of avoiding collisions when hashing. Another way is "linear probing" (and Knuth is cite

The linked list is crucial to the patent, as the "external chaining" way of avoiding collisions when hashing. Another way is "linear probing" (and Knuth is cited) but there's already a similar patent for that. It's a good idea (incremental garbage collection of expired records with each lookup, instead of batching it), but obvious. Good enough to be in a textbook, but only worth maybe one line. There might be some cleverness in the specifics of integrating it into the internals of maintaining the hashtable, but I haven't read the detailed description to check. ( http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=5,893,120.PN.&OS=PN/5,893,120&RS=PN/5,893,120 http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec... The idea is in three short paragraphs at "BRIEF SUMMARY OF THE INVENTION", and the problem is at "BACKGROUND OF THE INVENTION". The part I haven't read is "DETAILED DESCRIPTION OF THE INVENTION". I wish the specific details were given of the reasons for why this parent was held valid, how exactly linux was found to infringe.