Systems and methods for generating bit matrices for hash functions using fast filtering

A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

• receiving a collection of keys for multiple key-value pairs to be evaluated in a lookup circuit;
• receiving representations of two or more hash functions, each of which comprises a respective bit matrix and a respective bit vector;
• determining whether the two or more hash functions can be combined for use in the lookup circuit to map all keys in the collection to unique lookup addresses, including performing, for each of at least one key in the collection of keys:
• computing a first hash value bit vector by applying one of the two or more hash functions to the key;
• computing one or more other hash value bit vectors by applying respective other ones of the two or more hash functions to the key;
• and
• performing a union-find type operation to construct one or more graphs based on the first hash value bit vector and the one or more other hash value bit vectors to determine whether the first hash value bit vector and the one or more other hash value bit vectors belong to the same set, wherein nodes in the one or more graphs are distinct hash value bit vectors produced by the two or more hash functions from distinct keys in the collection and edges in the one or more graphs are the distinct keys in the collection that produced their respective connected nodes;
• wherein said computing the first hash value bit vector, said computing the one or more other hash value bit vectors, and said determining whether the first hash value bit vector and the one or more other hash value bit vectors belong to the same set are performed iteratively for respective keys in the collection of keys until:
• it is determined that, for one of the keys in the collection, the first hash value bit vector and the one or more other hash value bit vectors belong to the same set;
• or
• it is determined that, for all of the keys in the collection of keys, the first hash value bit vector and at least one of the one or more other hash value bit vectors belong to different sets;
• and
• returning, based on whether the first hash value bit vector and the one or more other hash value bit vectors belong to the same set, data indicating whether the two or more hash functions can be combined for use in the lookup circuit.

A system, comprising:

• one or more processors;
• and
• a memory coupled to the one or more processors and storing program instructions that when executed on the one or more processors cause the one or more processors to perform:
• receiving a collection of keys for multiple key-value pairs to be evaluated in a lookup circuit;
• receiving representations of two or more hash functions, each of which comprises a respective bit matrix and a respective bit vector;
• determining whether the two or more hash functions can be combined for use in the lookup circuit to map all keys in the collection to unique lookup addresses, including performing, for each of at least one key in the collection of keys:
• computing a first hash value bit vector by applying one of the two or more hash functions to the key;
• computing one or more other hash value bit vectors by applying respective other ones of the two or more hash functions to the key;
• and
• performing a union-find type operation to construct one or more graphs based on the first hash value bit vector and the one or more other hash value bit vectors to determine whether the first hash value bit vector and the one or more other hash value bit vectors belong to the same set, wherein nodes in the one or more graphs are distinct hash value bit vectors produced by the two or more hash functions from distinct keys in the collection and edges in the one or more graphs are the distinct keys in the collection that produced their respective connected nodes;
• wherein said computing the first hash value bit vector, said computing the one or more other hash value bit vectors, and said determining whether the first hash value bit vector and the one or more other hash value bit vectors belong to the same set are performed iteratively for respective keys in the collection of keys until:
• it is determined that, for one of the keys in the collection, the first hash value bit vector and the one or more other hash value bit vectors belong to the same set;
• or
• it is determined that, for all of the keys in the collection of keys, the first hash value bit vector and at least one of the one or more other hash value bit vectors belong to different sets;
• and
• returning, based on whether the first hash value bit vector and the one or more other hash value bit vectors belong to the same set, data indicating whether the two or more hash functions can be combined for use in the lookup circuit.