Lookups by collisionless direct tables and CAMs

A method of preventing collisions between two or more binary keys wherein each binary key corresponds to an action to be taken, comprising the steps of:

• providing a hash table having a plurality of entries indexed by a selected portion of hash values of said binary keys, each entry pointing to a location in a data structure for storing the non-selected portions of, or the entire hash value of, the binary key and action data corresponding to the value of the binary key, and a contact addressable memory (CAM) having a plurality of entries, each configured to store a binary key, or a value unique to a binary key, and an association to a corresponding action associated therewith;
• storing in said hash table a pointer to said data structure using a selected one portion of the hash values of binary keys as an index into the hash table when and only when said selected one portion of the hash value is not the selected one portion of the hash value of any other binary key, and storing in the CAM binary keys or values unique to said binary keys, and establishing an association between said CAM entry locations and locations of said data structures, when and only when the selected portion of the hash value of any such binary key is the same as the selected portion of the hash value of one or more other binary keys, and wherein an insertion of a new value in the CAM or hash table is accomplished by:
• seeking the value of the binary key in the cam;
• if the value is found, overwriting the key and associated action and the program ended;
• if the key is not found in the CAM, the key is hashed, the selected hash value is sought in the hash table, if the selected value is not found in the hash table, the selected value is written in the hash table with a pointer to the action and the remainder of the hash value, and the program is ended;
• if the selected portion of hash value is stored in the hash table with a pointer to the remainder of the hash value, the action is updated and the program ended;
• if the remainder of the hash value is different corresponding to a different action, then enter the key of the selected portion of the hash value being compared into the CAM with the associated activity, recreate the key from the hash value stored in the hash table and action, and enter the recreated key in the CAM and associated action and end the program.