Если вы не знакомы с universal hashing, это в основном попытка гарантировать небольшое количество столкновений (в противоположность, скажем, с использованием простого старого модуля), используя некоторую довольно простую математику, включающую случайность. Проблема заключается в том, что не работает для меня:Универсальное хэширование хуже, чем модульное хеширование, что не так?
size_t hash_modulo(const int value) {
return (size_t) (value % TABLE_SIZE);
}
// prime 491 is used because its > 128, which is the size of the hash table
size_t hash_universal(const int value) {
const size_t a = (size_t) (rand() % 491 + 1);
const size_t b = (size_t) (rand() % 491);
//printf("a: %zu, b:%zu\n", a, b);
return ((a * value + b) % 491) % TABLE_SIZE;
}
Я тест по модулю хеширования первого и определить наибольшую длину цепи (длина цепи означает, что размер хэш-ведро):
size_t get_max_chain_length(int input[TABLE_SIZE], size_t (*hash_function)(const int)) {
HashTable *hash_table = hash_table_create(hash_function);
if (!hash_table) {
return 0;
}
for (size_t i = 0; i < TABLE_SIZE; ++i) {
hash_table_add(hash_table, input[i]);
}
size_t maximum_chain_length = 0;
for (int j = 0; j < TABLE_SIZE; ++j) {
const size_t length = length_of_(hash_table->rows[j]);
maximum_chain_length = (length > maximum_chain_length) ? length : maximum_chain_length;
}
//hash_table_print(hash_table);
hash_table_destroy(hash_table);
return maximum_chain_length;
}
я выбрать один из входные данные, которые привели к действительно большой цепочке (id est, которая плохо работает с использованием простого модуля) и бросают это против универсального хэширования. Универсальное хеширование использует случайность, поэтому я могу принимать постоянный ввод и получать разные результаты.
И здесь возникает проблема. Я пробую 100 случайных входных массивов размером 128 каждый и рассчитываю среднюю самую длинную цепь и общую длинную цепь, но оба алгоритма выполняют аналогичные.
Вы можете проверить мою основную информацию в своем repo.
Мой вопрос: этот результат можно ожидать? Не делает ли универсальное хеширование лучше ни при каких входных данных, которые уже выполнялись с ошибкой, используя modulo? Или я просто испортил свою реализацию (скорее).
Большое спасибо!
Подождите, вы пересчитываете 'a' и' b' для каждого доступа к кешу? Как это имеет смысл? – melpomene
были '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '? – WhozCraig
@melpomene: Если они были статическими, функция всегда будет иметь один и тот же вход в одно ведро? – AdHominem