Проверка некоторых хеш-функций

[eddy_em]

И опять я со своим текстовым протоколом для МК, где крутить в цикле strcmp совсем неинтересно (особенно если команд под сотню). И со stackoverflow попал я на страничку, где приведено три варианта хеш-функций. Я набросал простенький код для проверки

#include <stdio.h>
#include <string.h>
#include <usefull_macros.h>

#define ALLOCSZ     (5000)

// djb2 http://www.cse.yorku.ca/~oz/hash.html
static uint32_t hash(const char *str){
    uint32_t hash = 5381;
    uint32_t c;
    while((c = (uint32_t)*str++))
        //hash = ((hash << 5) + hash) + c;
        // hash = hash * 19 + c;
        //hash = hash * 33 + c;
    return hash;
}

#if 0
static uint32_t hash(const char *str){ // sdbm
    uint32_t hash = 5381;
    uint32_t c;
    while((c = (uint32_t)*str++))
        hash = c + (hash << 6) + (hash << 16) - hash;
    return hash;
}
#endif



typedef struct{
    char str[32];
    uint32_t hash;
} strhash;

static int sorthashes(const void *a, const void *b){
    register uint32_t h1 = ((strhash*)a)->hash, h2 = ((strhash*)b)->hash;
    if(h1 > h2) return 1;
    else if(h1 < h2) return -1;
    return 0;
}

int main(int argc, char **argv){
    //char buf[32];
    initial_setup();
    if(argc != 2) ERRX("Usage: %s dictionary_file", argv[0]);
    mmapbuf *b = My_mmap(argv[1]);
    if(!b) ERRX("Can't open %s", argv[1]);
    char *word = b->data;
    strhash *H = MALLOC(strhash, ALLOCSZ);
    int l = ALLOCSZ, idx = 0;
    while(*word){
        if(idx >= l){
            l += ALLOCSZ;
            H = realloc(H, sizeof(strhash) * l);
            if(!H) ERR("realloc()");
        }
        char *nxt = strchr(word, '\n');
        if(nxt){
            int len = nxt - word;
            if(len > 31) len = 31;
            strncpy(H[idx].str, word, len);
            H[idx].str[len] = 0;
            //strncpy(buf, word, len);
            //buf[len] = 0;
        }else{
            //snprintf(buf, 31, "%s", word);
            snprintf(H[idx].str, 31, "%s", word);
        }
        H[idx].hash = hash(H[idx].str);
        //printf("word: %s\n", buf);
        //printf("%u\t%s\n", hash(buf), buf);
        //printf("%u\t%s\n", H[idx].hash, H[idx].str);
        ++idx;
        if(!nxt) break;
        word = nxt + 1;
    }
    qsort(H, idx, sizeof(strhash), sorthashes);
    --idx;
    strhash *p = H;
    for(int i = 0; i < idx; ++i, ++p){
        if(p->hash == p[1].hash){
            printf("Words '%s' and '%s' have same hashes: %u\n", p->str, p[1].str, p->hash);
        }
    }
    FREE(H);
    My_munmap(b);
    return 0;
}

Для проверки выдрал 43001 английское слово из файла русско-английского словаря (который у меня в веб-морде словаря используется: перевод между русским, английским и карачаевским).
Естественно, "простейший" алгоритм K&R дал огромное количество совпадений хешей. А вот оба оставшихся алгоритма ни одного совпадения не дали! По времени получилось совершенно одинаково: всего лишь 6мс на все про все, хоть в sdbm больше вычислений. У djb2 есть еще вариант с умножением (понятно, что на МК лучше это не тащить, ведь сдвиги гораздо быстрей). На ПК скорость была все те же 6мс. Я попробовал разные простые числа, и вот можно не 33 туда воткнуть, а 19 — уже с ним ни одного совпадения.
Наткнулся на интересную штуку: я и не подозревал, что strncpy и snprintf так разительно отличаются по скорости: если вместо strncpy я использую второй, то время увеличивается аж до 21 секунды!
Теперь надо еще сделать кодогенератор, который по заданному словарю будет мне генерировать заголовочный файл с хэшами (типа #define CMD_LIST (число), а число будет вычислять как hash("list");) и кусок сишного кода со switch'ем (и в пункте, соответствующем CMD_LIST, будет запускаться функция handler_list(str)).