У меня было странное представление о функции хеширования.Задача:
Вы сохраняете идентификационные номера 162 учеников в классе, получая n оценок из 300 в курсе (для каждого n = 0, 1, 2, ... 300)в хеш-таблице.Для этого разработайте простейшую хэш-функцию с наименьшей вероятностью столкновений, чтобы количество потерянных ячеек памяти также было минимальным.Здесь происходит столкновение, когда два студента, набравших n 1 и n 2 , получают одинаковый слот в хэш-таблице.
Можно использовать одно решениеh (n) = (n * 5 + 7)% 163 вместе с цепочкой.Может быть не более 162 различных отметок.
РЕДАКТИРОВАТЬ Существует несколько стандартных способов сделать это.Но я хотел бы попробовать свою идею и проверить ее (возможно, математически).У него могут быть меньшие столкновения с меньшей памятью.
Теперь вот идея, которая у меня была.Я могу предположить, что распределение оценок составляет гауссов .Итак, есть больше людей со средним баллом и меньше в крайних.
Итак, я могу иметь хеш-функцию примерно так:
h (n) = 0 (если n <100 || n> 200)
h (n) = 1 (если 100 <= n <125 || 175 <= n <200) <br>h (n) = 2 (если 125 <=n <140 || 160 <= n <175) <br>h (n) = 3 (если 140 <= n <160) </p>
Для некоторых таких условий (скажем, k)хэш-таблица будет иметь наименьшее количество столкновений и наименьшее количество занимаемого пространства.
Теперь это всего лишь предположение. Имеет ли смысл что-то подобное? Есть ли способ доказать это?Или я где то не прав?