Back to results
US 2013/0173908 A1Published application
Hash Table Organization
AssigneeBroadcom Corporation
InventorsBrad Matthews, Bruce Kwan, Puneet Agarwal
Life of this patent
Estimating the term…
Abstract
Disclosed are various embodiments for improving hash table utilization. A key corresponding to a data item to be inserted into a hash table can be transformed to improve the entropy of the key space and the resultant hash codes that can generated. Transformation data can be inserted into the key in various ways, which can result in a greater degree of variance in the resultant hash code calculated based upon the transformed key.
Claims20
A non-transitory computer-readable medium embodying a program executable in a computing device, the program comprising:
- code that generates a key associated with a data item, the key based at least upon a subset of data from the data item;
- code that calculates a first transformation action code, the first transformation action code corresponding to a first transformation action, the first transformation action corresponding to a manner in which a first transformation data is inserted into the key to form a first transformed key;
- code that calculates a second transformation action code, the second transformation action code corresponding to a second transformation action, the second transformation action corresponding to a manner in which a second transformation data is inserted into the key to form a second transformed key, wherein the first transformation action and the second transformation action each comprise one of:
- an append, a prepend, and an interleave;
- code that generates the first transformed key based at least upon the key and the second transformed key based at least upon the key, the first transformed key generated by modifying the key with the first transformation data by inserting the first transformation data into the key to form the first transformed key, and the second transformed key generated by modifying the key with the second transformation data by inserting the second transformation data into the key to form the second transformed key;
- code that calculates a first hash code based at least upon the first transformed key with a first hash function;
- code that calculates a second hash code based at least upon the second transformed key with a second hash function, wherein the first hash function is substantially orthogonal relative to the second hash function;
- code that inserts the data item in a first partition of a hash table in a first location corresponding to the first hash code;
- and
- code that inserts the data item in a second partition of the hash table in a second location corresponding to the second hash code.
7 more elements
A method, comprising:
- generating a key associated with a data item, the key based at least upon a subset of data from the data item;
- generating a first transformed key based at least upon the key and a second transformed key based at least upon the key, the first transformed key generated by modifying the key with first transformation data and the second transformed key generated by modifying the key with second transformation data;
- calculating a first hash code based at least upon the first transformed key with a first hash function;
- calculating a second hash code based at least upon the second transformed key with a second hash function;
- inserting the data item in a first partition of a hash table in a first location corresponding to the first hash code;
- and
- inserting the data item in a second partition of the hash table in a second location corresponding to the second hash code.
4 more elements
A network switch, comprising:
- at least one processor circuit;
- and
- a hash table accessible to the at least one processor circuit, the at least one processor circuit configured to:
- generate a key associated with a data item, the key based at least upon a subset of data from the data item;
- generate a first transformed key based at least upon the key and a second transformed key based at least upon the key, the first transformed key generated by modifying the key with first transformation data and the second transformed key generated by modifying the key with second transformation data;
- calculate a first hash code based at least upon the first transformed key with a first hash function;
- calculate a second hash code based at least upon the second transformed key with a second hash function;
- insert the data item in a first partition of a hash table in a first location corresponding to the first hash code;
- and
- insert the data item in a second partition of the hash table in a second location corresponding to the second hash code.
7 more elements
Dependencies are inferred from the claim text.