Patent ID: 11914647
Assignee: GOOGLE LLC
Field: Computer technology (Electrical engineering)
Classification: CPC G  H | IPC G

Claim 0:
1. A hash table system, comprising:
a plurality of hash tables, associated with respective hash functions, for storing key-value pairs;
an overflow memory for storing key-value pairs moved from the hash tables due to collision; and
an arbiter for arbitrating among commands including update commands for installing key-value pairs into the hash tables or uninstalling key-value pairs from the hash tables, match commands for matching keys to locations in the hash tables, and rehash commands for relocating key-value pairs from the overflow memory to the hash tables or relocating key-value pairs from one of the hash tables to another of the hash tables,
wherein for each system clock cycle, the arbiter selects as a selected command one of an update command, a match command, or a rehash command, and
wherein the hash table system completes execution of each selected command within a bounded number of system clock cycles.