Firmaets Facebook på open source hash tabel implementeringer optimeret til effektivt hukommelsesforbrug. F14 bruges i Facebook-infrastrukturen som erstatning for de fleste typer hash-tabeller og giver dig mulighed for at reducere hukommelsesforbruget uden at ofre ydeevnen. F14 overgår mærkbart google::sparse_hash_map hash-tabeller, som hidtil er blevet betragtet som de mest hukommelseseffektive. Projektkoden er skrevet i C++ og inkluderet i biblioteket .
F14 refererer til algoritmer med et kollisionsopløsningssystem baseret på dobbelt hashing med 14 (en celle i hash-tabellen gemmer en kæde på 14 slots, og intervallet mellem celler beregnes ved hjælp af en hjælpe-hash-funktion). For at fremskynde cellefiltreringsoperationer bruger implementeringen SSE2 vektorinstruktioner til x86_64-systemer og NEON til Aarch64-systemer, som giver dig mulighed for at parallelisere operationerne med at vælge slots med nøgleringe og screeningsnøgler inde i kæden. Blokke med 14 slots behandles ad gangen, hvilket er den optimale balance mellem effektiviteten ved at bruge processorcachen og antallet af kollisioner.
En funktion ved F14 er muligheden for at vælge forskellige datalagringsstrategier:
- F14NodeMap - bruger den mindste mængde hukommelse til store og mellemstore nøgler. Giver indirekte lagring af elementer med et opkald, hver gang malloc-funktionen indsættes;
- F14ValueMap - Giver minimalt hukommelsesforbrug til små taster. Elementer gemmes i selve cellerne (inline). For mellemstore og store taster fører denne tilgang til en mærkbar hukommelsesomkostning;
- F14VectorMap er hurtigere for store tabeller og komplekse nøgler, men langsommere for simple nøgler og små tabeller. Elementerne pakkes i et sammenhængende array og adresseres af en 32-bit indeksmarkør;
- F14FastMap er en kombineret strategi. Hvis nøglen er mindre end 24 bytes, er F14ValueMap valgt, og hvis mere, vælges F14VectorMap.
Kilde: opennet.ru