1. Вопросы и упражнения

1. Как будет вести себя программа, использующая поиск с хешированием, если из-за ошибки программирования значением хеш-функции всегда будет одна и та же константа?

2. Можно ли использовать хеширование в случае хранения данных на внешнем устройстве?

3. Почему требуется, чтобы хеш-функция принимала все значения из множества индексов I? Чем плохо, если она будет принимать, например, только четные значения?

4. Как можно реализовать удаление ключа из хешируемой таблицы? Для каких способов разрешения коллизий это сделать легче?

5. Почему значения функции двойного хеширования hh(x)должны быть взаимно просты с размером хеш-таблицы?

6. Разместить в хеш-таблице из 11 элементов следующие ключи: 60, 24, 77, 126, 100, 239, 2, 93. Использовать алгоритм деления и алгоритм линейных проб.

7. Дополнительные вопросы поиска

   1. Определение порядковых статистик

Порядковой статистикой порядка rдля массиваAназывается значение элемента массива, который должен был бы стоять наr-м месте, если бы массив был сортирован по возрастанию.

Некоторые из порядковых статистик имеют специальные названия. Понятно, что статистика порядка 1 – это просто минимальный элемент массива, а порядка n– максимальный элемент. Статистика порядкаn/2называетсямедианоймассива. Точнее говоря, при нечетномnмедиана – это статистика порядка(n+1)/2(средний по значению элемент массива), а при четномnмедианой можно назвать любой из двух средних по значению элементов.

Порядковые статистики порядка n/4и3n/4называются, соответственно, первой и третьейквартилямимассива.

Понятно, что задача определения порядковых статистик родственна задаче сортировки массива. Радикальным способом определения сразу всех порядковых статистик является именно сортировка, после которой нужная статистика определяется непосредственно по индексу. Таким образом, задача определения всех порядковых статистик имеет оценку времени T(n) = O(nlog(n)). Однако в тех случаях, когда требуется определить лишь одну или несколько статистик, сортировка является избыточным решением. Для этой задачи существуют более быстрые алгоритмы, которые являются как бы «облегченными версиями» алгоритмов сортировки.

Отметим для начала, что задача определения первой и последней статистик (т.е. минимального и максимального значений) выполняется за один проход по массиву и, стало быть, имеет оценку эффективности T(n) = O(n). Если ставится задача определения небольшого фиксированного числа «крайних» статистик (например, «найти три минимальных значения»), то можно, немного усложнив программу, по-прежнему справиться за один проход.

Более общая постановка задачи «найти kнаименьших (наибольших) значений» требует более регулярного подхода. Самое простое решение – выполнитьkпроходов алгоритма сортировки выбором (п. 3.2.2), после чего нужные элементы окажутся в начале таблицы. Оценка эффективности такого решенияT(k, n) = O(kn).

Другой способ решения той же задачи – применить в неполном виде алгоритм HeapSort(подразд. 3.5). Следует сначала выполнить фазу построения пирамиды, что потребует времениT(n) = O(n). Затем надо выполнитьkпроходов второй фазы алгоритма. Напомним, что каждый такой проход заключается в перестановке первого (максимального) элемента пирамиды с последним, после чего максимальный элемент исключается из пирамиды, а новый первый элемент просеивается через пирамиду за время порядкаO(log(n)). Таким образом,kнаибольших элементов будет найдена за времяT(k, n) = O(n + klog(n)). Обычно это получается быстрее, чем с помощью простого выбора.

Описанные подходы плохо подходят для таких задач, как определение медианы и квартилей. Поскольку для медианы k = n/2, неполныйHeapSortдает оценкуT(n) = O(nlog(n)), т.е. работает ненамного быстрее, чем полная сортировка. Лучшим решением здесь является использование неполного алгоритмаQuickSort(подразд. 3.4). Напомним, что в полномQuickSortпосле того, как массив разделен на две части, такое же разделение должно рекурсивно применяться к каждой из полученных частей. Для определения же, например, медианы массива интересна только одна из полученных частей, а именно та, которая включает в себя средний (по индексу) элемент массива. Только эта часть массива может включать в себя медианный элемент, поэтому только к ней следует применить следующую операцию разделения. Вместо рекурсивного разветвления имеем последовательное итеративное уточнение интервала, содержащего медиану. Можно ожидать, что этот алгоритм должен работать значительно быстрее обычногоQuickSort. На самом деле оказывается, что неполныйQuickSortобеспечивает в среднем линейное время отыскания медианы (или любой другой порядковой статистики с заданным номеромk):T_ср(n) = O(n). К сожалению, оценка для худшего случая гораздо хуже:T_макс(n) = O(n²). Однако в [3] описана достаточно заковыристая модификация неполногоQuickSort, которая обеспечивает линейную оценку времени отыскания порядковой статистики даже в худшем случае. Это достигается применением довольно сложной процедуры выбора разделяющего элемента.

Для большинства приложений можно довериться хорошей средней оценке обычного неполного QuickSortи не усложнять себе жизнь дополнительными ухищрениями. Исключение составляют те редкие случаи, когда даже маловероятная задержка выполнения абсолютно недопустима, и потому надо применять пусть сложную, но гарантированно быструю процедуру.