Хэш-функция

@Rt · Регистрация: 03.04.2020

Author24 — интернет-сервис помощи студентам

Я новичок в С++. Помогите пожалуйста.
Пусть m (размер хеш-таблицы) равен 2^p. Обозначим d=k^2 и представим d в виде двоичного числа. Тогда значением хеш-функции h(k) будет p битов средней части d.
У меня примерно получилось так

C++

int h(int key) { 
 
key =pow ( key,2); 
 
key >>= 5; // Отбрасываем 5 младших бит 
 
return key % pow ( 2,p); // Возвращаем p младших бит 
 
}

Но мне кажется не рационально отбрысывать 5 бит или для данной задачи я всё сделал правильно?

@oleg-m1973 · 13.04.2020, 13:33

Сообщение от Rt

Но мне кажется не рационально отбрысывать 5 бит или для данной задачи я всё сделал правильно?

Что такое "средняя часть d"?

Добавлено через 5 минут

C++

int h(int key) 
{
    const int d = key * key;
    //???????????key >>= 5; // Отбрасываем 5 младших бит
 
    //return d % m; 
    return d & ~(m - 1); //если m - степень двойки, >= 2 
}

	13.04.2020, 13:33