Dynamically adjusting hash table capacity

摘要

An example hashing unit includes a plurality of hardware-based hash tables, wherein each of the hash tables comprises a plurality of buckets, and wherein the plurality of hash tables comprise a set of zero or more active hash tables and a set of one or more inactive hash tables. An example hashing unit controller is configured to receive a key value to be stored in the hashing unit, determine that one of the inactive hash tables should be activated, and, based on the determination, activate the one of the set of inactive hash tables as a recently activated hash table, determine one of the buckets of the recently activated hash table to which a hash function associated with the recently activated hash table maps the received key value, and store the key value in the determined one of the buckets of the recently activated hash table.

主权项

1. A method comprising:
receiving, by a hashing unit controller executed by a processing unit, a key value to be stored in a hashing unit comprising a plurality of hardware-based hash tables, wherein each of the hash tables comprises a plurality of buckets, wherein the plurality of hash tables comprise a set of zero or more active hash tables and a set of one or more inactive hash tables, wherein each of the hash tables is associated with a respective one of a plurality of logic circuits that execute a respective one of a plurality of hash functions such that there is a one-to-one correspondence between the hash tables and the hash functions, and wherein the logic circuits associated with the active hash tables are powered on; determining that one of the inactive hash tables should be activated to increase an available hash space of the hashing unit, wherein the available hash space comprises the buckets of the active hash tables; based on the determination that the one of the inactive hash tables should be activated, activating the one of the set of inactive hash tables as a recently activated hash table, determining one of the buckets of the recently activated hash table to which the hash function associated with the recently activated hash table maps the received key value, and storing the key value in the determined one of the buckets of the recently activated hash table; determining that one of the active hash tables can be deactivated;
based on the determination that one of the active hash tables can be deactivated: extracting key values currently stored by the active hash table to be deactivated; storing the extracted key values to the active hash tables that are not to be deactivated; and deactivating the active hash table to be deactivated and powering off the logic circuit associated with the active hash table to be deactivated.