IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Как расчитать размер хэш таблицы
сообщение
Сообщение #1


Гость






Привет всем!
Проблема моя такова.

Имеетая программа создающая для файла из 200 слов хэш-таблицу. При этом подсчитывается количество коллизий. По заданию необходимо определить минимально необходимый объем хэштаблицы.
Вот я и не знаю как это сделать. Какое должно быть соотношение размер-коллизии для файла из 200 слов.
К примеру для таблицы из 300 эл количество коллизий равно 700, для таблицы из 400 эл количество равно 13
Но чем больше таблица тем больше памяти она расходует, так что же выбрать большее количество коллизий или меньшее значение хэша.

Уже неделю бъюсь нигде ничего не нашел про это.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Для начала следует определиться, что именно следует считать минимально необходимым объемом.
При хорошей хэширующей функции вероятность коллизии равна обратному размеру таблицы. Т.е. для таблицы из 100 входов вероятность коллизии 1%.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 14:48
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name