Patent ID: 7895211

Claim:
A computer implemented method for reinserting a chain into a hash table of a computer system, the chain including a plurality of keys, the hash table including a plurality of key fields and a plurality of link fields associated with the plurality of key fields, the hash table utilizing an initial collision resolution scheme that precludes the coalescing of chains, the method comprising: hashing at least a first key of the plurality of keys, a second key of the plurality of keys, and a third key of the plurality of keys, wherein hashes of the first key, the second key, and the third key result in a collision of the first key, the second key, and the third key, and wherein the first key is a median key value of the first key, the second key, and the third key; providing binary tree including a plurality of nodes corresponding to the plurality of keys of the chain, the plurality of nodes including a root node corresponding to the first key, and more than one child node corresponding to the second key and the third key; storing the first key in a corresponding home key field of the plurality of key fields; and storing the second key and the third key in two empty adjacent fields of the plurality of key fields and storing a first empty adjacent key value of the one of the two empty adjacent key fields in a corresponding home link field of the first key, the more than one child node corresponds to the second key and the third key.