Hash table organization
View Patent ↗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.
1. A non-transitory computer-readable medium storing a program that, when executed by a computing device, causes the computing device to:
receive a data item via a network;
generate a key based on a subset of data from the received data item;
calculate a first transformation action code, the first transformation action code corresponding to a first transformation action in which a first transformation data is inserted into the key to form a first transformed key;
calculate a second transformation action code, the second transformation action code corresponding to a second transformation action in which a second transformation data is inserted into the key to form a second transformed key;
generate the first transformed key according to the first transformation action code by inserting the first transformation data into the key;
generate the second transformed key according to the second transformation action code by inserting the second transformation data into the key;
calculate a first hash code based on the first transformed key with a first hash function;
calculate a second hash code based on the second transformed key with a second hash function that is orthogonal to the first 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.
2. The non-transitory computer-readable medium of claim 1 , wherein the program further causes the computing device to:
calculate a first transformation data selection code that is orthogonal to the first transformation action code;
select the first transformation data from a first transformation data table according to the first transformation data selection code;
calculate a second transformation data selection code that is orthogonal to the second transformation action code; and
select the second transformation data from a second transformation data table according to the second transformation data selection code.
3. The non-transitory computer-readable medium of claim 2 , wherein in the calculation of the first transformation data selection code and the calculation of the second transformation data selection code, the computing device further generates a respective hash code based on the key.
4. The non-transitory computer-readable medium of claim 2 , wherein each of the first transformation data table and the second transformation data table further comprises a respective table including a plurality of randomly generated data entries.
5. A method performed by processing circuitry, the method comprising:
receiving a data item via a network;
generating, by the processing circuitry, a key based on a subset of data from the received data item;
generating, by the processing circuitry, a first transformed key by inserting first transformation data into the key;
generating, by the processing circuitry, a second transformed key by inserting second transformation data into the key;
calculating, by the processing circuitry, a first hash code based on the first transformed key with a first hash function;
calculating, by the processing circuitry, a second hash code based on the second transformed key with a second hash function that is orthogonal to the first 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.
6. The method of claim 5 , further comprising:
calculating a first transformation action code, the first transformation action code corresponding to a first transformation action in which the first transformation data is inserted into the key to form the first transformed key; and
calculating a second transformation action code, the second transformation action code corresponding to a second transformation action in which the second transformation data is inserted into the key to form the second transformed key, wherein
the processing circuitry generates the first transformed key according to the first transformation action code, and
the processing circuitry generates the second transformed key according to the second transformation action code.
7. The method of claim 6 , further comprising:
calculating a first transformation data selection code that is orthogonal to the first transformation action code;
selecting the first transformation data from a first transformation data table according to the first transformation data selection code;
calculating a second transformation data selection code that is orthogonal to the second transformation action code; and
selecting the second transformation data from a second transformation data table according to the second transformation data selection code.
8. The method of claim 7 , wherein each of the first transformation data table and the second transformation data table further comprises a respective table including a plurality of randomly generated data entries.
9. The method of claim 7 , wherein calculating the first transformation data selection code and calculating the second transformation data selection code each further comprise generating a respective hash code based on the key.
10. The method of claim 6 , wherein the first transformation action and the second transformation action further comprise an action from a group of actions including an append, a prepend, and an interleave.
11. The method of claim 6 , wherein calculating the first transformation action code and calculating the second transformation action code each further comprise generating a respective hash code based on the key.
12. The method of claim 5 , wherein the key includes a subset of data fields extracted from the data item received via the network switch.
13. 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:
receive a data item via a network;
generate a key based on a subset of data from the received data item;
generate a first transformed key by inserting first transformation data into the key;
generate a second transformed keg by inserting second transformation data into the key;
calculate a first hash code based on the first transformed key with a first hash function;
calculate a second hash code based on the second transformed key with a second hash function that is orthogonal to the first 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.
14. The network switch of claim 13 , wherein
the at least one processor circuit is further configured to:
calculate a first transformation action code, the first transformation action code corresponding to a first transformation action in which the first transformation data is inserted into the key to form the first transformed key; and
calculate a second transformation action code, the second transformation action code corresponding to a second transformation action in which the second transformation data is inserted into the key to form the second transformed key, and
the at least one processor circuit generates the first transformed key according to the first transformation action code and generates the second transformed key according to the second transformation action code.
15. The network switch of claim 14 , wherein the at least one processor circuit is further configured to:
calculate a first transformation data selection code that is orthogonal to the first transformation action code;
select the first transformation data from a first transformation data table according to the first transformation data selection code;
calculate a second transformation data selection code that is orthogonal to the second transformation action code; and
select the second transformation data from a second transformation data table according to the second transformation data selection code.
16. The network switch of claim 15 , wherein each of the first transformation data table and the second transformation data table further comprises a respective table including a plurality of randomly generated data entries.
17. The network switch of claim 14 , wherein the first transformation action and the second transformation action further comprise an action from a group of actions including an append, a prepend, and an interleave.
18. The network switch of claim 13 , wherein the key includes a subset of data fields extracted from the data item received via the network.