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