Книга: Системное программное обеспечение. Лабораторный практикум

Выводы по проделанной работе

Выводы по проделанной работе

В результате выполнения написанного программного кода для ряда тестовых файлов было установлено, что при заполнении таблицы идентификаторов до 20 % (до 45 идентификаторов) для поиска и размещения идентификатора с использованием рехэширования на основе генератора псевдослучайных чисел в среднем требуется меньшее число сравнений, чем при использовании хэш-адресации в комбинации с бинарным деревом. При заполнении таблицы от 20 % до 40 % (примерно 45–90 идентификаторов) оба метода имеют примерно равные показатели, но при заполнении таблицы более, чем на 40 % (90-223 идентификаторов), эффективность комбинированного метода по сравнению с методом рехэширования резко возрастает. Если на входе имеется более 223 идентификаторов, рехэширование полностью перестает работать.

Таким образом, установлено, что комбинированный метод работоспособен даже при наличии простейшей хэш-функции и дает неплохие результаты (в среднем 3–5 сравнений на входных файлах, содержащих 500–700 идентификаторов), в то время как метод на основе рехэширования для реальной работы требует более сложной хэш-функции с диапазоном значений в несколько тысяч или десятков тысяч.

Оглавление книги