Updating a perfect hash data structure, such as a multi-dimensional perfect hash data structure, used for high-speed string matching

Apparatus for inserting a representation of a new rule, defined as a set of at least one new transition corresponding to the new rule, each of the at least one new transition of the set being from a source state to a destination state, into a perfect hash table which includes previously placed transitions, each of the previously placed transitions being from a source state to a destination state, to generate an updated perfect hash table, the apparatus comprising:

• a) at least one processor;
• and
• b) a non-transitory storage device storing processor-executable instructions which, when executed by the at least one processor, cause the at least one processor to perform a method including, for each of the at least one new transition of the new rule:
• 1) hashing the new transition ;
• 2) determining whether the hashed new transition conflicts with any of the previously placed transitions;
• 3) responsive to a determination that there is no conflict,
• inserting the hashed new transition into the perfect hash table, and otherwise, responsive to a determination that the hashed new transition conflicts with any of the previously placed transitions,
• A) determining whether or not the state associated with the new transition has more transitions than a state associated with the conflicting transition, and
• B) responsive to a determination that the state associated with the new transition has equal or more transitions than the state associated with the conflicting transition,
• i) removing from the hash table any transitions of the state associated with the conflicting transition,
• ii) placing the hashed new transition into the perfect hash table, and
• iii) re-placing the removed transitions into the hash table such that the hash table is maintained as a perfect hash table,
• otherwise, responsive to a determination that the state associated with the new transition has fewer transitions than the state associated with the conflicting transition,
• i) removing any previously placed transitions of the state associated with the new transition, and
• ii) re-placing the transitions of the state associated with the new transition into the hash table such that the hash table is maintained as a perfect hash table.