Новая таблица имеет коэффициент заполнения 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).
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Например, с помощью поиска в ширину можно: