СТА: Лекция №6 - Хэш-таблицы

Версия 2.0, 17 сентября 2013г.

(С) 2012-2013, Зайченко Сергей Александрович, к.т.н, ХНУРЭ, доцент кафедры АПВТ

Мотивация

Практическое применение алгоритмов поиска с линейной вычислительной сложностью весьма ограничено. Фактически, линейный поиск пригоден лишь для обработки очень малых объемов данных, поскольку в худшем случае для N хранимых элементов выполняется N сравнений ключей. Если число элементов не превышает 10, использование для поиска таких простых структур данных, как массив или связный список, может быть оправдано минимумом служебных вычислений, необходимых для функционирования, а также простотой реализации.

Алгоритм бинарного поиска существенно более эффективен, однако требует наличия заранее упорядоченных данных. В общем случае, реальные данные не будут упорядочены, а время их сортировки может существенно превысить приемлемые для задачи пороговые значения.

Если число элементов превышает 10, о характере хранимых данных-ключей неизвестно никакой дополнительной информации, ключи не упорядочены ни по какому критерию, то необходимо задуматься об использовании более сложной структуры данных для реализации отображений и множеств. Одной из таких структур являются хэш-таблицы.

Как будет показано далее, реализация отображений и множеств на основе хэш-таблиц значительно сложнее реализации на основе массивов или связных списков. Также, хэш-таблицы требуют существенно большего объема памяти для функционирования, а в процессе поиска выполняют большее число служебных действий для обеспечения своей работы. Если речь идет о малом количестве элементов, применение такой структуры данных может быть нерациональным как с точки зрения памяти, так и времени. Однако, для больших отображений и множеств все усилия полностью окупаются значительно лучшей эффективностью - в среднем, время поиска ключа в хэш-таблице вообще не зависит от количества хранимых ключей (O(1) - константная вычислительная сложность). При грамотной реализации, производительность поиска в хэш-таблице на большом количестве ключей (тысячи, десятки тысяч и более) будет предпочтительнее бинарного поиска, при этом не потребуется предварительного упорядочивания.

Константной вычислительной сложностью O(1) также обладает случай реализации отображений и множеств, в котором ключи ставятся в прямое соответствие с индексами массива. Однако, в общем случае, пространство всех возможных ключей может быть слишком большим, например, весь возможный диапазон числа типа int. Чтобы выделить для каждого возможного ключа по ячейке потребуется очень большой объем памяти. Даже если предположить, что среда выполнения имеет доступ к огромным объемам оперативной памяти, большая часть ячеек в таком массиве бы не использовалась, и память расходовалась бы напрасно.