Лемма 14.2 В хеш-таблице, использующей раздельное связывание, содержащей М списков и N ключей, вероятность того, что количество ключей в каждом списке незначительно отличается от N/M, очень близка к 1.

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

\ }

к выбирается из N элементов: эти к элементов помещаются в данный список с вероятностью а остальные N - к элементов не помещаются в данный список с вероятностью 1 - (1/Л/). Обозначив a=N/M, это выражение можно переписать как

которое, в соответствии с классической аппроксимацией Пуассона (Poisson), меньще чем

ае-

Отсюда следует, что вероятность наличия в списке более чем / а элементов меньще чем

Эта вероятность исключительно мала для используемых на практике диапазонов параметров. Например, если средняя длина списков равна 20, вероятность хеширования в какой-либо список, содержащий более 40 элементов, меньше чем (40e/2)V24 0.0000016.

Приведенный анализ - пример классической задачи занятости, при которой рассматривается Л мячей, произвольно забрасываемых в одну из М корзин, и анализируется распределение мячей по корзинам. Классический математический анализ этих задач предоставляет много других интересных фактов, имеющих отношение к изучению алгоритмов хеширования. Например, в соответствии с аппроксимацией Пуассона количество пустых списков близко к Еще интереснее, что среднее количество элементов, вставленных прежде, чем происходит первое совпадение, равно прибли-

зительно = 1.25 Л/ Этот результат - решение классической задачи о дне

рождения. Например, в соответствии с этими же рассуждениями, при М = 365 среднее количество людей, которых придется проверить, прежде чем удастся найти двух с оди-

маковыми датами рождения, приблизительно равно 24. В соответствии со вторым классическим результатом среднее количество элементов, вставленных прежде, чем в каждом списке окажется, по меньшей мере, по одному элементу, приблизительно равно МНм- Этот результат - решение классической задачи коллекционера карточек. Например, в соответствии с этим анализом при М = 1280, вероятно, придется собрать 9898 бейсбольных карточек (купонов), прежде чем удастся заполучить по одной карточке для каждого из 40 игроков каждой из 32 команд в серии. Полученные результаты весьма показательны для проанализированных свойств хеширования. На практике, в соответствии с ними, раздельное связывание можно успешно использовать, если хеш-функция создает значения, близкие к случайным {см. раздел ссылок).

Как правило, в реализациях раздельного связывания значение М выбирают достаточно малым, чтобы не приходилось напрасно расходовать огромные непрерывные области памяти с пустыми связями, но достаточно большим, чтобы последовательный поиск был наиболее эффективным методом для списков. Гибридные методы (такие, как использование бинарных деревьев вместо связных списков), вероятно, не стоят беспокойства. В качестве руководящего принципа, значение М можно выбирать равным приблизительно одной пятой или одной десятой количества ключей, ожидаемого в таблице, чтобы каждый из списков предположительно в среднем содержал около пяти или десяти ключей. Одно из достоинств раздельного связывания в том, что это решение не критично: при наличии большего количества ключей, чем ожидалось, поиски будут занимать несколько больше времени, чем если бы заранее был выбран больший размер таблицы; при наличии в таблице меньшего количества ключей поиск будет выполняться еще быстрее при, вероятно, небольшом объеме напрасно расходуемой памяти. Когда объем памяти не является критичным, значение М может бьггь выбрано достаточно большим, чтобы время поиска было постоянным; когда же объем памяти критичен, все же можно повысить производительность в М раз, выбрав значение М максимально допустимым.

Приведенные в предыдущем абзаце комментарии применимы ко времени поиска. На практике для раздельного связывания обычно применяются неупорядоченные списки по двум основным причинам. Во-первых, как уже упоминалось, операция insert выполняется исключительно быстро: мы вычисляем хеш-функцию, выделяем память для узла и связываем узел с началом соответствующего списка. Во многих приложениях шаг распределения памяти не требуется (поскольку элементами, вставленными в таблицу символов, могут быть существующие записи с доступными полями связей), и для выполнения операции insert остается выполнить всего три или четыре машинные инструкции. Второе важное преимущество использования в профамме 14.3 реализации с использованием неупорядоченных списков в том, что все списки работают подобно стекам, поэтому можно легко удалить последние вставленные элементы, которые размещаются в начале списков (см. упражнение 14.21). Эта операция важна при реализации таблицы символов со вложенными диапазонами, например в компиляторе.

Как и в нескольких предшествующих реализациях, мы неявно предоставляем клиенту выбор способа обработки дублированных ключей. Клиент, подобный программе 12.11, может выполнить операцию search для проверки наличия дубликатов перед выполнением любой операции insert, убеждаясь, что таблица не содержит дублирован-

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

В общем случае хеширование не подходит для использования в приложениях, в которых требуются реализации операций sort и select для АТД. Однако хеширование часто используется в типовых ситуациях, когда необходимо использовать таблицу символов с потенциально большим количеством операций search, insert и remove с последующим однократным выводом элементов в порядке их оючей. Одним из примеров такого приложения является таблица символов в компиляторе; другой пример - программа удаления дубликатов, подобная программе 12.11. Для обработки этой ситуации в реализации раздельного связывания с использованием неупорядоченных списков следовало бы воспользоваться одним из методов сортировки, описанных в главах 6-10. В реализации с использованием упорядоченного списка сортировку можно было бы выполнить за время, пропорциональное N\gM в случае сортировки слиянием списка (см. упражнение 14.23).

Упражнения

> 14.16 Сколько времени могло бы потребоваться в худшем случае для вставки ключей в первоначально пустую таблицу при использовании раздельного связывания с (/) неупорядоченными списками и ( ) упорядоченными списками?

> 14.17 Приведите содержимое хеш-таблицы, образованной при вставке элементов с ключами EASYQUTIONb указанном порядке в первоначально пустую таблицу, состоящую из iV = 5 списков при использовании раздельного связывания с неупорядоченными списками. Для преобразования к-юл буквы алфавита в индекс таблицы используйте хеш-функцию Wkmad М.

> 14.18 Выполните упражнение 14.17, но для случая упорядоченных списков. Зависит ли ответ от порядка вставки элементов?

о 14.19 Создайте программу, которая с исгюльзованием раздельного связывания вставляет Л случайных целых чисел в таблицу размером Уу/ЮО, а затем определяет длину самого короткого и самого длинного списков, при 7V = 10, 10 10 и 10

14.20 Измените программу 14.3 с целью исключения из нее заглавных связей путем представления таблицы символов в виде массива узлов (nodes) (каждая запись таблицы - первый узел в ее списке).

14.21 Измените программу 14.3, включив в нее для каждого элемента целочисленное поле, значение которого устанавливается равным количеству элементов в таблице в момент вставки элемента. Затем реализуйте функцию, которая удаляет все элементы, для которого значение этого поля больше заданного целого числа N.

14.22 Измените реализацию функции search в программе 14.3, чтобы она отображала все элементы, ключи которых равны данному ключу, так же, как это делает функция show.

14.23 Разработайте реализацию таблицы символов, использующую раздельное связывание с упорядоченными списками (при фиксированном размере таблицы, равном 97), которая включает деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции construct, count, search, insert, remove, join, select и sort для АТД первого класса таблицы символов при поддержке дескрипторов клиента (см. упражнения 12.6 и 12.7).