hash maps

оказывается, ассоциативные массивы с ключом-строкой могут быть быстрее unordered_map <std::string, int>

unordered_map <std:string, int> map1;
 
    printf("std hash func... ");
 
    clock_t t0=clock();
 
    for(i=0;i < n;i++)
        str = ltoa(i);
        map1[str]=i;
    } 

если хранить индекс, как int со значением из хэш-функции, то можно достигать до 4х-кратного повышения скорости работы

unordered_map <uint32_t, int> map3_3;
 
    printf("X31_hash_string hash func... ");
 
    clock_t t20_3=clock();
 
    for(i=0;i < n ; i++)
        str = ltoa(i);
        map3_3[X31_hash_string((char*)str.c_str())]=i;
    }

и функция расчета хэша, которую я взял из проекта khash.h, выглядит просто и работает быстро и создаёт мало коллизий:

typedef uint32_t khint_t;
 
uint32_t X31_hash_string(const char *s)
{
 
    khint_t h = *s;
    if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
    return h;
} 

xxhash оказался не очень быстрым, хоть и качественный, почти как и другие сравниваемые алгоритмы хеширования
sz означает количество элементов
если их меньше 5000000 - количество добавляемых элементов - то коллизии-наложения и ошибки
fletcher32 оказался не очень быстрым и к тому же создаёт много коллизий. не нужен!
X31_hash_string оказалась и быстрее, и хороша - мало коллизий(0)

скачать source code of tests on c++