Company Facebook on open source hash table implementations optimized for efficient memory consumption. F14 is used in the Facebook infrastructure as a replacement for most types of hash tables and allows you to reduce memory consumption without sacrificing performance. F14 noticeably outperforms google::sparse_hash_map hash tables, which have so far been considered the most memory efficient. The project code is written in C++ and included in the library .
F14 refers to algorithms with a collision resolution system based on double hashing with 14 (one cell of the hash table stores a chain of 14 slots, and the interval between cells is calculated using an auxiliary hash function). To speed up cell filtering operations, the implementation uses SSE2 vector instructions for x86_64 systems and NEON for Aarch64 systems, which allow you to parallelize the operations of selecting slots with key chains and screening keys inside the chain. Blocks of 14 slots are processed at a time, which is the optimal balance between the efficiency of using the processor cache and the number of collisions.
A feature of F14 is the ability to choose different data storage strategies:
- F14NodeMap - consumes the least amount of memory for large and medium sized keys. Provides indirect storage of elements with a call each time the malloc function is inserted;
- F14ValueMap - Provides minimal memory consumption for small keys. Elements are stored in the cells themselves (inline). For medium and large keys, this approach leads to a noticeable memory overhead;
- F14VectorMap is faster for large tables and complex keys, but slower for simple keys and small tables. The elements are packed into a contiguous array and addressed by a 32-bit index pointer;
- F14FastMap is a combined strategy. If the key is less than 24 bytes, then F14ValueMap is selected, and if more, F14VectorMap is selected.
Source: opennet.ru