Hashing scheme using compact array tables

摘要

Embodiments include a method, system, and computer program product for creating an array table. In one embodiment the method includes identifying keys associated with values in a database and identifying bits common between the plurality of keys using logical functions and removing the common bits to form condensed keys. The method also includes modulating the condensed keys using identified common bits to create transformed keys and populating the plurality of array tables using the transformed keys and associated values.

主权项

1. A computer program product for creating a plurality of array tables, the computer program product comprising: a non-transitory computer readable storage medium having program code embodied therewith, the program code comprising instructions that when executed by a processor cause the processor to:
identifying keys in a database, the keys each having an associated value; identifying bits that are assigned common values between the keys; removing the identified bits to form condensed keys; modulating the bits of the condensed keys until at least a subset of the modulated bits of the condensed keys have a uniform distribution; replacing the subset of the modulated bits in each of the condensed keys with a result obtained by applying a particular function to both the subset of the modulated bits and remaining bits of each of the condensed keys not in the subset; associating each replaced subset of modulated bits with each of a plurality of partitions based on the value of the replaced subset of modulated bits such that all keys with a same value for the replaced subset of modulated bits will be disposed in the same partition; and using any remaining bits of the modulated condensed keys and the associated values in each partition to populate the corresponding one of the array tables associated with that partition.