Построение хэш-таблицы/хэш-функции

Question

Я хотел бы построить хеш-таблицу, которая ищет ключи в последовательностях (строках) байтов в диапазоне от 1 до 15 байт.

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

Любая помощь была бы значительно увеличена.

Максимальное число записей в хеша: 4081 * 15 + 4081 * 14 + ... = 4081 4081 ((15 * (16))/2) = 489720.

Так, например:

int table[489720]; 

int lookup(unsigned char *key) 
{ 
    int index = hash(key); 
    return table[index]; 
} 

Что такое хороший выбор для хеш-функции или как я могу ее построить?

Спасибо.

Answer 1

Если вы хотите идеальный хеш, то вы можете начать с чтения статьи в Википедии по адресу perfect hashing. Если вы столкнетесь с корягами, вы можете попросить о помощи здесь.

Answer 2

Если среднее число строк, находящихся в таблице, является низким - например, менее 10 000 записей - ассоциативный массив будет разумным подходом, даже если использовать линейный поиск, если он находится на современной архитектуре процессора.

В противном случае построение «идеального хеша» требует проверки каждого символа строки и вычисления уникального значения на основе возможного диапазона. Например, если только A..Z 26 символов допускается в ключе, это будет работать:

int 
hash (const char *key) 
{ 
    int h = 0; 
    while (key && *key) 
     h = h * 26 + (*key++ - 'A'); 
    return h; 
} 

Answer 3

Ваш ключ пространство является большим (около 2^(8 * 15)), так что если вы хотите идеальный хеш, вам нужно будет знать, какие 489720 действительных ключей будут отображаться заранее. Даже тогда практически невозможно найти идеальный хэш для этих клавиш, даже если вы позволили значительно увеличить таблицу (a.k.a. очень низкий коэффициент нагрузки). Единственный способ, которым я знаю, найти идеальный хэш - это пробная версия и ошибка, и случайный хеш, скорее всего, потерпит неудачу, если ваша таблица не будет близка к 489720^2 записям.

Я настоятельно рекомендую использовать regular (non-perfect) hash и deal with collisions appropriately, например. с цепочкой:

struct entry { 
    unsigned char *key; 
    int value; 
    struct entry *next; 
} *table[1<<20]; 
int lookup(unsigned char *key) { 
    int index = hash(key) % (1<<20); 
    for (struct entry *e = table[index]; e != NULL; e = e->next) { 
    if (!strcmp(key, e->key)) return e->value; 
    } 
    // not found 
} 

Я также рекомендую вам не осуществить это самостоятельно - использовать стандартную библиотеку как c++ hashmap.

Answer 4

хэш строки C, я всегда использовал эту функцию (взять% результат размера вашей хэш-таблицы в):

int hashstring(const char* s) { 
    int key = 0; 
    while (*s) { 
    key = key*37 + *s++; 
    } 
    return key; 
} 

Я не помню, где я получил его от первоначально, но во многих лет это меня не подвело.