• если связанные списки становятся слишком длинными, работа с хеш-таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции!
Хеш-функции играют важную роль. Хорошая хеш-функция создает минимальное число коллизий. Как же выбрать хорошую хеш-функцию? Об этом в следующем разделе!
Быстродействие
Глава началась с примера магазинчика. Вы хотели построить механизм, который мгновенно выдает цены на продукты. Что ж, хеш-таблицы работают очень быстро.
В среднем хеш-таблицы выполняют любые операции за время O(1). Время O(1) называется постоянным. Ранее примеры постоянного времени вам еще не встречались. Оно не означает, что операции выполняются мгновенно; просто время остается постоянным независимо от размера хеш-таблицы. Например, вы знаете, что простой поиск выполняется за линейное время.
Бинарный поиск работает быстрее — за логарифмическое время:
Поиск данных в хеш-таблице выполняется за постоянное время.
Видите горизонтальную линию? Она означает, что при любом размере хеш-таблицы — 1 элемент или 1 миллиард элементов — выборка данных займет одинаковое время. На самом деле вы уже сталкивались с постоянным временем: получение элемента из массива выполняется за постоянное время. От размера массива оно не зависит. В среднем случае хеш-таблицы работают действительно быстро.
В худшем случае все операции с хеш-таблицей выполняются за время O(n) (линейное время), а это очень медленно. Сравним хеш-таблицы с массивами и списками.
Взгляните на средний случай для хеш-таблиц. При поиске хеш-таблицы не уступают в скорости массивам (получение значения по индексу). А при вставке и удалении они так же быстры, как и связанные списки. Получается, что они взяли лучшее от обеих структур! Но в худшем случае хеш-таблицы медленно выполняют все эти операции, поэтому очень важно избегать худшего случая быстродействия при работе с хеш-таблицами. А для этого следует избегать коллизий. Для предотвращения коллизий необходимы:
• низкий коэффициент заполнения;
• хорошая хеш-функция.
примечание
Материал следующего раздела не является обязательным. Речь пойдет о том, как реализовать хеш-таблицу, но вам никогда не придется делать это самостоятельно. Какой бы язык программирования вы ни выбрали, в нем найдется готовая реализация хеш-таблиц. Вы можете воспользоваться встроенной реализацией хеш-таблицы, не сомневаясь в том, что она имеет хорошую эффективность. А в следующем разделе мы заглянем во внутреннее устройство хеш-таблиц.
Коэффициент заполнения
Коэффициент заполнения хеш-таблицы вычисляется по простой формуле.
Хеш-таблицы используют массив для хранения данных, поэтому для вычисления коэффициента заполнения можно подсчитать количество заполненных элементов в массиве. Например, в следующей хеш-таблице коэффициент заполнения равен 2/5, или 0,4.
Скажите, каков коэффициент заполнения этой таблицы?
Если вы ответили «1/3» — все правильно. По коэффициенту заполнения можно оценить количество пустых ячеек в хеш-таблице.
Предположим, в хеш-таблице нужно сохранить цены 100 товаров и хеш-таблица состоит из 100 элементов. В лучшем случае каждому товару будет выделен отдельный элемент.
Коэффициент заполнения этой хеш-таблицы равен 1. А если хеш-таблица состоит всего из 50 элементов? Тогда ее коэффициент заполнения будет равен 2. Выделить под каждый товар отдельный элемент ни при каких условиях не удастся, потому что элементов попросту не хватит! Коэффициент заполнения больше 1 означает, что количество товаров превышает количество элементов в массиве.
С ростом коэффициента заполнения в хеш-таблицу приходится добавлять новые элементы, то есть изменять ее размер. Представим, что эта хеш-таблица приближается к заполнению.
Хеш-таблицу необходимо расширить. Расширение начинается с создания нового массива большего размера. Обычно в таком случае создается массив вдвое большего размера.
Теперь все эти элементы необходимо заново вставить в новую хеш-таблицу функцией hash:
Новая таблица имеет коэффициент заполнения 3/8. Гораздо лучше! С меньшим коэффициентом загрузки число коллизий уменьшается, и ваша таблица начинает работать более эффективно. Хорошее приближенное правило: изменяйте размер хеш-таблицы, когда коэффициент заполнения превышает 0,7. Но ведь на изменение размеров уходит много времени, скажете вы, и будете абсолютно правы! Да, изменение размеров требует значительных затрат ресурсов, поэтому оно не должно происходить слишком часто. В среднем хеш-таблицы работают за время O(1) даже с изменением размеров.
Хорошая хеш-функция
Хорошая хеш-функция должна обеспечивать равномерное распределение значений в массиве.
Плохая хеш-функция создает скопления и порождает множество коллизий.
Какую хеш-функцию считать хорошей? К счастью, вам об этом никогда не придется беспокоиться — пусть об этом беспокоятся пожилые бородатые умники, сидящие в полутемных комнатах. Если вам интересна эта тема, поищите информацию об алгоритме SHA (короткое описание приведено в последней главе). Вы можете использовать этот алгоритм в своей хеш-функции.
Упражнения
Очень важно, чтобы хеш-функции обеспечивали хорошее распределение. Они должны распределять значения как можно шире. Худший случай — хеш-функция, которая отображает все значения на одну позицию в хеш-таблице.
Предположим, имеются четыре хеш-функции, которые получают строки:
1. Первая функция возвращает «1» для любого входного значения.
2. Вторая функция возвращает длину строки в качестве индекса.
3. Третья функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с «a», хешируются в одну позицию, все строки, начинающиеся с «b» — в другую и т.д.
4. Четвертая функция ставит в соответствие каждой букве простое число: a = 2, b = 3, c = 5, d = 7, e = 11 и т.д. Для строки хеш-функцией становится остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки «bag» будет вычислен индекс 3+2+17%10 = 22%10 = 2.
В каком из этих примеров хеш-функции будут обеспечивать хорошее распределение? Считайте, что хеш-таблица содержит 10 элементов.
5.5 Телефонная книга, в которой ключами являются имена, а значениями – номера телефонов. Задан следующий список имен: Esther, Ben, Bob, Dan.
5.6 Связь размера батарейки с напряжением. Размеры батареек: A, AA, AAA, AAAA.
5.7 Связь названий книг с именами авторов. Названия книг: «Maus», «Fun Home», «Watchmen».
Шпаргалка
Вам почти никогда не придется реализовать хеш-таблицу самостоятельно. Язык программирования, который вы используете, должен предоставить необходимую реализацию. Вы можете пользоваться хеш-таблицами Python, и при этом вам будет обеспечена производительность среднего случая: постоянное время.
Хеш-таблицы чрезвычайно полезны, потому что они обеспечивают высокую скорость операций и позволяют по-разному моделировать данные. Возможно, вскоре выяснится, что вы постоянно используете их в своей работе.
• Хеш-таблица создается объединением хеш-функции с массивом.
• Коллизии нежелательны. Хеш-функция должна свести количество коллизий к минимуму.
• Хеш-таблицы обеспечивают очень быстрое выполнение поиска, вставки и удаления.
• Хеш-таблицы хорошо подходят для моделирования отношений между объектами.
• Как только коэффициент заполнения превышает 0,7, пора изменять размер хеш-таблицы.
• Хеш-таблицы используются для кэширования данных (например, на веб-серверах).
• Хеш-таблицы хорошо подходят для обнаружения дубликатов.
6. Поиск в ширину
В этой главе
• Вы научитесь моделировать сети при помощи новой абстрактной структуры данных — графов.
• Вы освоите поиск в ширину — алгоритм, который применяется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к X?»
• Вы узнаете, чем направленные графы отличаются от ненаправленных.
• Вы освоите топологическую сортировку — другой алгоритм сортировки, раскрывающий связи между узлами.
Эта глава посвящена графам. Сначала вы узнаете, что такое граф. Затем я покажу первый алгоритм, работающий с графами. Он называется поиском в ширину (BFS, Breadth-First Search).
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Например, с помощью поиска в ширину можно:
• написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;
• реализовать проверку правописания (минимальное количество изменений, преобразующих ошибочно написанное слово в правильное, например АЛГОРИФМ -> АЛГОРИТМ — одно изменение);
• найти ближайшего к вам врача.
Одни из самых полезных алгоритмов, известных мне, работают с графами. Внимательно прочитайте несколько следующих глав — этот материал неоднократно пригодится вам в работе.
Знакомство с графами
Предположим, вы находитесь в Сан-Франциско и хотите добраться из Твин-Пикс к мосту Золотые Ворота. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Возможные варианты:
Какой алгоритм вы бы использовали для поиска пути с наименьшим количеством шагов?
Можно ли сделать это за один шаг? На следующем рисунке выделены все места, в которые можно добраться за один шаг.
Мост на этой схеме не выделен; до него невозможно добраться за один шаг. А можно ли добраться до него за два шага?
И снова мост не выделен, а значит, до него невозможно добраться за два шага. Как насчет трех шагов?
Ага! На этот раз мост Золотые Ворота выделен. Следовательно, чтобы добраться из Твин-Пикс к мосту по этому маршруту, необходимо сделать три шага.