查看文章

Recent work has shown that perfect hashing and retrieval of data values associated with a key can be done in such a way that there is no need to store the keys and that only a few bits of additional space per element are needed. We present FiRe – a new, very simple approach to such data structures. FiRe allows very fast construction and better cache efficiency. The main idea is to substitute keys by small fingerprints. Collisions between fingerprints are resolved by recursively handling those elements in an overflow data structure. FiRe is dynamizable, easily parallelizable and allows distributed implementation without communicating keys. Depending on implementation choices, queries may require close to a single access to a cache line or the data structure needs as low as 2.58 bits of additional space per element.