Хеширование для индексов массива

Question

В моей программе на C у меня есть четыре 8-битных (char) переменных, выделенных в структуре. Если я хочу хэшировать эти числа, чтобы создать ключи (представляющие целые структуры), которые будут индексировать массив, как мне это сделать? (В программе много таких структур, поскольку мне часто приходится искать в таблице символов, чтобы увидеть, существуют ли они, если я не хочу создавать других, я не знал, какой алгоритм хеширования использовать, если я 'd хотите выполнить поиск по ключевым словам).

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

Но мне нужно что-то менее «тяжелое» ... этот метод кажется слишком напрасным, и я думаю, что это не так подходит для создания индексов массива.

Не правда ли? Существует ли еще один вид хеш-функций, который также занимает меньше памяти, чем 32 бита, если это возможно?

Answer 1

Возможно, вы захотите взглянуть на это list of hash functions.

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

Конечно, вы можете использовать любую функцию, чтобы превращать ваши символы в произвольное целочисленное представление, но если это представление не меняется для разных входов, вы эффективно получаете производительность связанного списка (представьте, используя одно из других предложений с размер таблицы 256, и ни одна из структур не меняется в байте 4). В чем вы беспокоитесь о 32-битных хэшах? Конечно, вы бы использовали hash%tablesize для индексирования?

Обычно вы не использовали бы криптографическую хеш-функцию (например, md5, sha-1). Просто выберите одну из некристаллических хеш-функций (например, Pearson/Jenkins hash).

/* jenkins hash, copied from http://en.wikipedia.org/wiki/Jenkins_hash_function */ 
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len) 
{ 
    uint32_t hash, i; 
    for(hash = i = 0; i < len; ++i) 
    { 
    hash += key[i]; 
    hash += (hash << 10); 
    hash ^= (hash >> 6); 
    } 
    hash += (hash << 3); 
    hash ^= (hash >> 11); 
    hash += (hash << 15); 
    return hash; 
} 

Side Примечание: Если у вас есть хорошее распределение хэш-значение, а также убедитесь, что размер хэш-таблицы достаточно велик. Вы увидите, что производительность ухудшается по мере того, как заполнение (коэффициент нагрузки) массива приближается к 1, поскольку вероятность хэш-коллизий будет возрастать.

Answer 2

Одна из возможностей, которую я не считаю ОП описывающей, состояла в том, чтобы объединить 4 значения char в одно 32-разрядное целое число, а затем mod, что с размером хэш-таблицы (предположительно простого числа) :

unsigned int combined = (c1 << 24) | (c2 << 16) | (c3 << 8) | (c4); 
unsigned int hashval = combined % hashtablesize; 

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

Answer 3

Почему бы вам не разместить структуры в массиве?

#include <stdio.h> 

typedef struct { 
    char a,b,c,d; 
} item; 
item items[20]; 

int main(int argc, char *argv[]) 
{ 
    items[0].a = 4; 
    items[0].b = 6; 
    items[0].c = 1; 
    items[0].d = 3; 
    // ... 
    items[4].a = 12; 
    // ... 
    printf("%d %d %d %d\n", items[0].a, items[0].b, items[0].c, items[0].d); 
    return 0; 
} 

Очевидно, что это решение с меньшим объемом памяти, так как данные хранятся непосредственно в основном массиве, так что нет никакой необходимости хеширования индексов, так как индекс массива делает работу без памяти потребление.

Конечно, вы можете использовать указатели, некоторые векторные функции C++ и т. Д. Но это самый простой и эффективный способ.

Единственный нюанс в том, что вы должны знать размер массива (количество элементов у вас будет) или там-удет-не-более-чем-XXX максимум ...

Answer 4

Существует ли еще один вид хэш-функций, который также занимает меньше памяти , чем 32 бит, если это возможно?

Это иллюзорная проблема. Ключ - это индекс массива - он нигде не хранится, он рассчитывается на основе поиска. Массивы в C являются непрерывными блоками, доступ к отдельным элементам основан на начале массива и размере типа, умноженного на индекс.

Для получения ключа, просто привести значение в беззнаковое 32-битный тип (не просто использовать int или unsigned int, как размер не обязательно 32 бита):

#include <inttypes.h> 
char x[4] = { 'A', 'B', 'C', 'D' }; 
uint32_t *key = (uint32_t*)&x;   

Затем сделать модуль на основе на размер стола.