Large database search using content addressable memory and hash

A circuit for searching an external memory containing search results based on a search value received from an external controller, comprising:

• a hash means for generating a hash output based on the search value, wherein said hash means is also for operationally connecting to input bus means for connecting the circuit to the external controller;
• a content addressable memory (CAM means for storing a CAM database of instances of the search values known to cause hash collisions in said hash means and for matching the search value against said CAM database such that a CAM output is provided if a match exists, wherein said CAM means is also for operationally connecting to said input bus means;
• a logic means for:
• receiving any said CAM output provided, creating an address value based there on, and providing said address value on output bus means for operationally connecting the circuit to the external memory, wherein said address value represents an address in the external memory;
• and otherwise
• receiving said hash output, creating one or more hash addresses based there on, for receiving a hash pointer value and creating said address value based there on, and for receiving a hash hit signal and responsive there to providing said address value on said output bus means;
• a search data storage means for:
• storing a plurality of said hash pointer values, wherein said hash pointer values represent instances of said hash addresses;
• storing a plurality of search data values, wherein said search data values represent instances of the search values;
• receiving a said hash address from said logic means and based there on retrieving a said hash pointer value and providing it to said logic means;
• and
• retrieving a said search data value based on said hash pointer value;
• and
• a comparator means for operationally connecting to said input bus means and for receiving the search value there from, for receiving said search data value from said search data storage means, for comparing the search value and said search data value to determine whether a match exists and, if a said match exists, for providing said hash hit signal to said logic means.

A circuit to search an external memory containing search results based on a search value received from an external controller, comprising:

• a plurality of serially connected hash units each able to receive an input value and generate a hash value based there on, wherein said input value includes all or part of the search value or a said hash value of a prior said hash unit, and wherein the last said hash value is a hash output;
• a plurality of content addressable memory (CAM) units equaling said hash units, whereby each said CAM unit has a paired said hash unit;
• said CAM units each to store a CAM database of instances of said input values known to cause hash collisions in its paired said hash unit;
• said CAM units further each to receive a said input value common with its paired said hash unit, to match said input value against its said CAM database, and to provide a CAM output if a match exists;
• a logic unit to receive said hash output and said CAM outputs and create an address value based there on, wherein said address value represents an address in the external memory;
• and
• said logic unit further to provide said address value on an output bus connecting the circuit to the external memory.

A circuit for searching an external memory containing search results based on a search value received from an external controller, comprising:

• a plurality of serially connected hash means for each receiving an input value and generating a hash value based there on, wherein the first said hash means operationally connects to input bus means for connecting the circuit to the external controller and wherein said input value includes all or part of the search value or a said hash value of a prior said hash unit, and wherein the last said hash value is a hash output;
• a plurality of content addressable memory (CAM) means, equaling said hash means, whereby each respective said CAM means is definable as having a paired said hash mean;
• said CAM means for storing a CAM database of instances of said input values known to cause hash collisions in its paired said hash means;
• said CAM means further for receiving a said input value common with its paired said hash means, for matching said input value against its said CAM database, and for providing a CAM output if a match exists;
• a logic means for receiving said hash output and said CAM outputs and for creating an address value based there on, wherein said address value represents an address in the external memory;
• and
• said logic means further for providing said address value on output bus means for connecting the circuit to the external memory, thereby permitting finding the search results in the external memory.