36 results about "Perfect hash function" patented technology

A recursively partitioned static router-table, the data structure incorporating a first-level partition including subtries and an auxiliary trie. A node of the subtrie includes a path Q(N) from the root R of a trie T to a root N of the subtrie, a stride s for a next-level partition, a mask that characterizes a next-level perfect hash function, and a pointer to the hash table for the next-level partition. At least one of the trie T, the first-level partition, the auxiliary trie, and the next-level partition is represented by a base structure selected from the group consisting of MBT and HSST.

Hardware circuitry may evaluate minimal perfect hash functions mapping keys to addresses in lookup tables. The circuitry may include primary hash function sub-circuits that apply linear hash functions to input key values (using carry-free arithmetic) to produce primary hash values. Each sub-circuit may multiply bit vectors representing key values by a bit matrix and add a constant bit vector to the result. The circuitry may include a secondary hash function sub-circuit that generates secondary hash values by aggregating values associated with multiple primary hash values using signed, unsigned, or modular integer addition, or bit-wise XOR operations. Secondary hash values may be usable to access data values in the lookup table that are associated with particular input key values. The circuitry may determine the validity of input keys and may alter the configuration or contents of the lookup tables. The hash function sub-circuits may include programmable hash tables.

A “Variable-Rate Perfect Hasher” maps sparse variable-rate data of one or more dimensions into a hash table using a perfect hash function. In various embodiments, perfect hash tables are populated by first computing offset table address for each data point of a domain of sparse variable-rate data elements. Offset vectors are then computed for each offset table address based in part on the size of each data element by evaluating offset vectors in order of a sum of the data point addresses mapping to each offset vector. These offset vectors are then stored in the offset table. For each data point, the corresponding offset vector is then used to compute a hash table address. Data elements are then perfectly hashed into the hash table using the computed hash table addresses. The resulting hash tables support efficient random access of the variable-sized data elements stored therein.