Фацебоок компанија о имплементацији хеш табела отвореног кода , оптимизован за ефикасну потрошњу меморије. Ф14 се користи у инфраструктури Фејсбука као замена за већину типова хеш табела и може да смањи потрошњу меморије без жртвовања перформанси. Ф14 приметно надмашује хеш табеле гоогле::спарсе_хасх_мап, које су до сада сматране најефикаснијим у погледу потрошње меморије. Код пројекта је написан у Ц++ и укључен је у библиотеку .
Ф14 се односи на алгоритме са системом за решавање колизија заснованим на двоструком хеширању са 14 (ланац од 14 слотова се чува у једној ћелији хеш табеле, а интервал између ћелија се израчунава помоћу помоћне хеш функције). Да би се убрзале операције филтрирања ћелија, имплементација користи векторске инструкције ССЕ2 за к86_64 системе и НЕОН за Аарцх64, које омогућавају паралелно извршавање операција за одабир слотова са ланцима кључева и одређивање кључева унутар ланца. Блокови од 14 слотова се обрађују истовремено, што је оптимална равнотежа између ефикасности коришћења кеш меморије процесора и броја колизија.
Посебна карактеристика Ф14 је могућност избора различитих стратегија складиштења података:
- Ф14НодеМап - троши најмање меморије за велике и средње тастере. Обезбеђује да се елементи чувају индиректно са позивом маллоц-а при сваком уметању;
- Ф14ВалуеМап - обезбеђује минималну потрошњу меморије за мале кључеве. Елементи се чувају у самим ћелијама (инлине). За средње и велике тастере, овај приступ доводи до приметних трошкова меморије;
- Ф14ВецторМап - ради брже за велике табеле и сложене кључеве, али спорије за једноставне кључеве и мале табеле. Елементи су спаковани у континуирано попуњени низ и адресирани помоћу 32-битног индексног показивача;
- Ф14ФастМап је комбинована стратегија. Ако је кључ мањи од 24 бајта, тада је изабран Ф14ВалуеМап, а ако је више, изабран је Ф14ВецторМап.
Извор: опеннет.ру