Back to results
US 2015/0032989 A1Published application
Methods, Systems, and Products for Hashing Using Twisted Tabulation
AssigneeAT&T Intellectual Property I, L.P.
InventorsMikkel Thorup, Mihai Patrascu
Life of this patent
Estimating the term…
Abstract
Methods, systems, and products describe a robust solution for the dictionary problem of data structures. A hash function based on tabulation is twisted to utilize an additional xoring operation and a shift. This twisted tabulation offers strong robustness guarantees over a set of queries in both linear probing and chaining.
Claims20
A method, comprising:
- retrieving, by a router, a hash function;
- generating, by the router, a tabulation of the hash function;
- generating, by the router, keys from the tabulation;
- denoting, by the router, heads in the keys;
- twisting, by the router, the heads to generate a twisted hash function;
- and
- storing, by the router, the twisted hash function.
4 more elements
A system, comprising:
- a processor;
- and
- a memory storing code that when executed causes the processor to perform operations, the operations comprising:
- retrieving a hash function;
- generating a tabulation of the hash function;
- generating keys from the tabulation;
- denoting heads in the keys;
- twisting the heads to generate a twisted hash function;
- and
- storing the twisted hash function.
7 more elements
A memory storing code which when executed causes a processor to perform operations, the operations comprising:
- retrieving a hash function;
- generating a tabulation of the hash function;
- generating keys from the tabulation;
- denoting heads in the keys;
- twisting the heads to generate a twisted hash function;
- and
- storing the twisted hash function.
4 more elements
Dependencies are inferred from the claim text.