Patent ID: 9135833
Filing Date: 2015-09-15
Classification: G06F,G09C,H04L

Abstract:
1. A method implemented by a network element to identify a set of bit indices for forming compressed keys, the compressed keys are used to map a set of keys of corresponding input values to assigned lookup values in a hash table, where the keys of the input values have colliding hash values according to a hash function of the hash table, the method comprising the steps of: receiving the set of keys having colliding hash values; traversing bits of the set of keys to find a best split bit index that most closely splits the set of keys into equal subset at a current level of the array of bit indices; splitting the set of keys into two subsets according to the best split bit index for the current level; checking whether all of the set of keys have been split into separate subsets; adding a selected best split bit to a bit index, for subsets larger than one key; tallying alternate split bits at a combine level for each subset of the keys; and selecting a bit with a highest tally to add to bit index.