Книга: «Алгоритмы с нуля»

Привет, Хаброжители!

Погрузитесь в мир алгоритмов! Разберитесь в их принципах, особенностях проектирования и практического применения.

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

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

Кому адресована книга

Эта книга предназначена для максимально широкого круга людей, которым интересен мир информатики и алгоритмов. Мы писали ее для следующих категорий читателей.

• Учащиеся. Если вы школьник, только начинающий изучать информатику, или студент высшего учебного заведения — эта книга послужит вам учебником, в котором в простой и доступной форме объясняются фундаментальные алгоритмические идеи и методы. Речь идет о темах, составляющих основу многих учебных программ по информатике, принятых во всем мире.
• Преподаватели. Если вы преподаватель, обучающий новые поколения ученых-информатиков, то эта книга станет для вас ценным источником сведений. Благодаря пошаговым объяснениям, примерам из реальной жизни и практическим задачам она послужит отличным справочником по планированию учебной программы и полезным дополнением к учебным лекциям.
• Профессионалы. Вы разработчик программного обеспечения, аналитик данных или профессионал в области технологий, желающий улучшить свое алгоритмическое мышление и навыки решения задач? Или, может быть, вы готовитесь к техническому собеседованию, посвященному структурам данных и алгоритмам? Эта книга послужит источником необходимых знаний и поможет освежить в памяти фундаментальные понятия.
• Самоучки. Если вы любитель, обучающийся самостоятельно (возможно, вы подумываете о смене карьеры или являетесь программистом-самоучкой, который хочет лучше понимать алгоритмы), то книга поможет вам в этом и гарантирует, что вы получите базовые знания.
• Предприниматели в сфере технологий. Основатели стартапов и менеджеры по продукту, работающие в технологических компаниях, благодаря базовому пониманию алгоритмов смогут принимать более взвешенные решения о разработке продукта, видеть возможности и ограничения своего программного обеспечения и более эффективно взаимодействовать с техническими специалистами в команде.

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

Если вы не уверены в своих математических познаниях или являетесь новичком в программировании — не волнуйтесь. Мы начнем с самых основ и простым и понятным языком объясним все необходимые математические или программные концепции. Хорошо, если у вас есть опыт программирования, но это не обязательное условие. Основное внимание мы уделим описанию концепций, а для иллюстрации идей используем псевдокод — простые обобщенные представления алгоритмов.

Читая эту книгу, помните: изучение алгоритмов представляет собой не просто запоминание процедур, а освоение нового способа мышления и решения задач. Решайте задачи, наслаждайтесь процессом и не бойтесь совершать ошибки. Именно так мы учимся, совершенствуемся и в результате осваиваем любые области.

Мы рады, что вы отправились с нами в это приключение по миру алгоритмов, и нам не терпится увидеть, куда вас приведут новые знания!

АЛГОРИТМЫ ПОИСКА

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

Алгоритмы поиска — обширная область программирования, в которой используется множество методов. Каждый из них имеет сильные и слабые стороны и конкретные варианты применения. Глубина понимания данной темы, умение анализировать алгоритмы поиска и выбирать правильный могут существенно повлиять на эффективность программ, особенно работающих с большими наборами данных.

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

Линейный поиск

Линейный поиск, также известный как последовательный поиск, — это простой, но эффективный метод поиска определенного значения в списке. Он последовательно проверяет каждый элемент списка, пока не найдет совпадение или не достигнет конца списка. Этот метод особенно полезен, когда количество элементов в списке не очень велико.

Кроме того, поскольку линейный поиск не требует сортировки списка, его можно использовать вместе с неотсортированными данными. Одно из преимуществ этого алгоритма — его легко реализовать с помощью цикла, поэтому его часто используют люди, которые только начинают изучать программирование. Более того, простота его реализации облегчает отладку, что может быть полезно при работе над крупными и сложными программами.

Еще одно преимущество линейного поиска — его легко адаптировать под конкретные потребности. Например, его можно использовать для поиска первого появления значения в списке или всех вхождений искомого значения. Такая гибкость делает его универсальным инструментом, который можно применять для решения широкого спектра задач, как простых, так и сложных.

Проиллюстрируем вышесказанное примером кода на Python:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i # вернуть индекс найденного элемента
    return -1 # вернуть -1, если элемент не найден

# Тестирование функции
arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170]
target = 110

result = linear_search(arr, target)
if result != -1:
    print("Элемент находится по индексу", str(result))
else:
    print("Элемента нет в массиве")

В этом примере определяется функция с именем linear_search, которая принимает массив и целевое значение. Она проверяет каждый элемент массива, пока не найдет элемент, соответствующий искомому. Найдя целевое значение, она возвращает его индекс в массиве; в противном случае возвращается -1, указывающее, что целевое значение отсутствует в массиве.

Важно отметить, что линейный поиск — не самый эффективный алгоритм, когда речь заходит о больших наборах данных. Фактически в худшем случае (когда искомое значение находится в конце списка или вообще отсутствует) ему придется проверить все элементы в списке, что может занять много времени и привести к временной сложности O(n), где n — размер списка.

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

Стоит упомянуть конкретные сценарии, в которых линейный поиск может быть особенно полезен.

• Небольшие списки. Линейный поиск обычно считается менее эффективным, чем более сложные алгоритмы, такие как двоичный поиск или поиск в хеш-таблицах, но короткие списки может обрабатывать лучше всего.
  
  Это связано с тем, что накладные расходы на сортировку списка или построение хеш-таблицы, совершенно необходимые для двоичного поиска или поиска в хеш-таблице соответственно, могут перевесить преимущества сложных алгоритмов, когда списки невелики. Фактически линейный поиск по-прежнему широко используется в ряде приложений, где небольшие списки являются нормой, например во встраиваемых системах или некоторых инструментах обработки данных.
  
  Линейный поиск проще в реализации и более понятен для тех, кто плохо знаком с программированием или не имеет опыта работы в области информатики. Поэтому для больших списков линейный поиск не самый эффективный вариант, а вот с маленькими списками он справляется отлично.
• Неупорядоченные данные. Как упоминалось выше, линейный поиск не требует сортировки входных данных. Когда они изначально не упорядочены и их сортировка нецелесообразна (например, из-за ограничений памяти или динамического характера данных), вполне можно использовать линейный поиск.
  
  Это связано с тем, что данный алгоритм последовательно просматривает входные данные, пока не найдет целевой элемент. Это свойство делает его особенно полезным, когда входные данные не организованы в определенном порядке, поскольку алгоритм все равно найдет нужный элемент, ничего дополнительно не обрабатывая или не сортируя.
  
  Кроме того, линейный поиск в небольших наборах данных часто выполняется быстрее, чем другие алгоритмы поиска. Это связано с отсутствием накладных расходов на сортировку. Однако важно отметить, что большие наборы данных линейный поиск может обрабатывать неэффективно из-за его временной сложности, O(n). В таких случаях стоит использовать другие алгоритмы поиска, такие как двоичный поиск или поиск в хеш-таблице.
• Последовательный доступ к памяти. Современные процессоры имеют сложную систему кэширования, и иногда последовательный доступ к памяти (как при линейном поиске) происходит быстрее, чем перемещения в разные концы списка (как при двоичном поиске). Однако это во многом зависит от конкретной архитектуры системы, а также характера и размера данных.
  
  Более того, эффективность последовательного доступа к памяти может меняться в зависимости от приложения и типа данных, к которым осуществляется доступ. Например, доступ к последовательным данным может быть более эффективным при работе с большими смежными блоками памяти, как при чтении или записи файлов. В то же время произвольный доступ может оказаться более эффективным при работе с меньшими объемами данных или при поиске определенных фрагментов информации в большем наборе данных.
  
  Важно отметить еще и то, что последовательный доступ к памяти подойдет не везде. В некоторых случаях затраты на его поддержание могут перевесить преимущества, особенно в системах, использующих сложные алгоритмы кэширования. Более того, на эффективность последовательного доступа к памяти может влиять и конкретная реализация алгоритма. Поэтому, выбирая стратегию доступа, важно учесть конкретные требования приложения.
• Потоковая передача данных, или передача данных в реальном времени. Линейный поиск можно использовать, когда данные передаются в режиме реального времени или полный набор данных недоступен на момент поиска, поскольку он не требует наличия всего набора данных, в отличие от алгоритмов двоичного поиска или поиска в хеш-таблицах.
  
  Линейный поиск — это алгоритм поиска определенного значения в списке, последовательности или массиве путем последовательной проверки каждого элемента, пока не будет найдено совпадение или достигнут конец списка. Поэтому линейный поиск особенно полезен в случаях, когда данные не отсортированы или ожидается, что пространство поиска будет ограничено несколькими значениями.
  
  Кроме того, линейный поиск легко распараллелить — его можно разделить на более мелкие задачи и выполнять их одновременно на нескольких процессорах, что ускорит процесс поиска. Однако стоит отметить, что на больших или отсортированных наборах данных линейный поиск может работать медленнее других алгоритмов, таких как двоичный поиск.

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

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

Ограничения линейного поиска

Несмотря то что линейный поиск прост и в ряде случаев полезен, у него есть определенные ограничения.

Масштабируемость

Линейный поиск — широко используемый алгоритм, особенно когда дело касается обработки небольших наборов данных. Однако он не самый эффективный — по мере увеличения объема данных может замедляться. Это связано с тем, что алгоритм последовательно проверяет каждый элемент, затрачивая много времени и ресурсов.

Это может быть серьезной проблемой в приложениях, обрабатывающих большие объемы данных, таких как анализ больших данных и машинное обучение. Поэтому при обработке больших объемов важно подумать о возможности применения альтернативных алгоритмов. Например, двоичный поиск — более эффективный алгоритм, позволяющий значительно сократить время поиска в больших наборах данных.

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

Скорость

Временная сложность линейного поиска равна O(n), то есть затрачиваемое им время растет линейно по мере увеличения объема входных данных. Это не идеальный вариант при работе с большими наборами данных, где более эффективные алгоритмы могут справляться с той же задачей быстрее. Например, алгоритм двоичного поиска имеет временную сложность O(log n), что позволяет выполнять поиск быстрее.

Другие, более сложные алгоритмы, такие как поиск в хеш-таблицах, могут работать еще быстрее. По мере увеличения объема данных разница в скорости между этими алгоритмами становится все заметнее. Поэтому важно учитывать размер набора данных при выборе подходящего алгоритма поиска.

Отсутствие оптимизации

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

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

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

Двоичный поиск

Двоичный поиск — это алгоритм, более эффективный, чем линейный поиск, при соблюдении определенных условий. Он следует принципу «разделяй и властвуй», о котором мы подробно говорили в главе 4.

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

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

Как и было обещано, теперь рассмотрим пример работы двоичного поиска и некий код, который поможет проиллюстрировать этот процесс.

Предположим, у нас есть отсортированный список чисел:

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

и нам нужно найти число 23.

1. Сначала проверим средний элемент списка, то есть 16. Поскольку 23 > 16, мы знаем, что число 23 должно находиться в правой половине списка.
2. Далее проверим середину правой половины — число 38. Поскольку 23 < 38, мы знаем, что число 23 должно находиться в левой половине оставшегося подсписка ([23, 38]).
3. Затем проверим середину списка [23, 38] — число 23. Поскольку 23 == 23, то мы считаем, что искомая цель найдена и поиск окончен.

Теперь посмотрим, как реализовать этот алгоритм на Python:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid # Элемент найден, вернуть его индекс
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1 # Элемент не найден

# Тестирование функции
numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(bunary_search(numbers, 23)) # Выведет 5

В этом фрагменте кода на Python мы определяем функцию binary_search, которая принимает отсортированный список arr и целевое значение target. Первым делом функция присваивает указателям left и right индексы первого и последнего элементов списка соответственно. Затем входит в цикл, который продолжается до тех пор, пока указатели left и right не встретятся.

В каждой итерации цикла вычисляется индекс среднего элемента mid. Если этот элемент равен целевому, то функция возвращает его индекс. Если искомое значение больше, то в указатель left записывается индекс mid + 1. Если меньше, то в указатель right записывается индекс mid — 1. Если цикл завершился, так и не найдя целевого значения, то функция возвращает -1, тем самым сообщая, что цель не найдена.

А теперь оценим производительность алгоритма двоичного поиска и сравним его с другими поисковыми алгоритмами.

Данный алгоритм демонстрирует значительное улучшение временной сложности по сравнению с линейным поиском. Каждое сравнение сокращает пространство поиска вдвое. Следовательно, чтобы найти искомое значение в списке из n элементов или убедиться в его отсутствии, в худшем случае потребуется проверить log2(n) элементов.

Учитывая эту логарифмическую зависимость между размером списка и количеством шагов, мы говорим, что двоичный поиск имеет временную сложность O(log n). Помните, что здесь подразумевается логарифм по основанию 2, но в нотации «O большое» эта деталь обычно игнорируется, поскольку нас больше интересуют темпы роста, а не конкретные величины.

С точки зрения пространственной сложности алгоритм двоичного поиска тоже показывает себя с лучшей стороны: ему требуется постоянный объем дополнительного пространства для хранения переменных left, right и mid, независимо от размера списка. Соответственно, пространственная сложность равна O(1).

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

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

Хеширование и хеш-таблицы

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

Хеш-функция — это математическая функция, которая принимает входное значение, обычно строку или число, и возвращает результат фиксированного размера — хеш-значение. Затем оно используется в качестве индекса для доступа к данным в памяти. Идеальная хеш-функция должна равномерно распределять данные по памяти, чтобы избежать коллизий, когда двум ключам назначается один и тот же индекс. Однако найти идеальную хеш-функцию — непростая задача, и для обработки коллизий используются различные методы, такие как объединение в цепочку или открытая адресация.

Объединение в цепочку — это метод сохранения нескольких значений с одним и тем же индексом в форме связанного списка. При возникновении коллизии новое значение просто добавляется в конец связанного списка. Открытая адресация, в свою очередь, предполагает поиск следующего доступного индекса при возникновении коллизии. Это можно сделать с помощью различных алгоритмов, таких как линейное или квадратичное зондирование. Более подробно об этих методах мы поговорим чуть позже.

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

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

Одно из преимуществ использования хеш-таблиц — возможность хранить пары «ключ — значение», что может пригодиться во многих приложениях. Например, хеш-таблицу можно использовать для хранения сведений о человеке, указывая его имя в качестве ключа, а информацию о нем, такую как его адрес, номер телефона и адрес электронной почты, — в качестве значения. Это позволит быстро получить данные о человеке, просто выполнив поиск по его имени.

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

В целом хеш-таблица — важный инструмент информатики, который используется в самых разных приложениях. Независимо от объема данных, хеш-таблицы позволят вам быстро и эффективно сохранять и извлекать данные.

Вот пример реализации простой хеш-функции и простой хеш-таблицы на Python:

# Определить простую хеш-функцию
def simple_hash(key):
    return key % 10

# Инициализировать хеш-таблицу как список с десятью элементами
hash_table = [None] * 10

# Добавить некоторые данные
key = 35
value = "Apple"

# Вычислить индекс
index = simple_hash(key)

# Сохранить значение value в хеш-таблицу
hash_table[index] = value

print(hash_table)

Этот код выведет:

[None, None, None, None, None, 'Apple', None, None, None, None]

В этом примере, чтобы определить, где сохранить значение «Apple», мы использовали простую хеш-функцию key % 10. Ключ key равен 35, а 35 % от 10 равно 5, поэтому значение «Apple» сохраняется в элементе списка с индексом 5.

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

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

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

Коллизии

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

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

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

Рассмотрим некоторые стратегии разрешения коллизий более подробно.

Объединение в цепочку

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

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

Вот пример:

# Пример реализации хеш-таблицы на Python
# с использованием метода объединения в цепочку
hash_table = [[] for _ in range(10)]

def insert(hash_table, key, value):
    hash_key = hash(key) % len(hash_table)
    key_exists = False
    bucket = hash_table[hash_key]
    for i, kv in enumerate(bucket):
        k, v = kv
        if key == k:
            key_exists = True
            break
    if key_exists:
        bucket[i] = ((key, value))
    else:
        bucket.append((key, value))

# Вставить несколько значений
insert(hash_table, 10, 'Apple')
insert(hash_table, 25, 'Banana')
insert(hash_table, 20, 'Cherry')

В этом случае оба ключа, 10 и 20, будут хешированы в один и тот же индекс (0), поэтому для обработки коллизии новая пара «ключ — значение» будет добавлена в конец списка, соответствующего индексу.

Открытая адресация

Открытая адресация — один из методов разрешения коллизий в хеш-таблицах. В соответствии с ним все пары «ключ — значение» хранятся в самой хеш-таблице, а при возникновении коллизии хеш-функция ищет следующий доступный слот в таблице. Существуют разные способы поиска следующего пустого слота, называемые последовательностями зондирования.

Один из таких способов — линейное зондирование, когда хеш-функция последовательно проверяет каждый слот в массиве, пока не встретит первый незанятый. Другой способ — это квадратичное зондирование, когда хеш-функция проверяет слоты, совершая переходы на всё бо́льшие расстояния. Наконец, еще одна последовательность зондирования — двойное хеширование, когда одна хеш-функция использует вторую для определения последовательности проверок.

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

Рассмотрим пример:

# Пример реализации хеш-таблицы на Python, использующей
# линейное зондирование для разрешения коллизий
hash_table = [None] * 10

def insert(hash_table, key, value):
    hash_key = hash(key) % len(hash_table)
    while hash_table[hash_key] is not None:
        hash_key = (hash_key + 1) % len(hash_table)
    hash_table[hash_key] = value

# Вставить несколько значений
insert(hash_table, 10, 'Apple')
insert(hash_table, 25, 'Banana')
insert(hash_table, 20, 'Cherry')

В этом случае если два ключа отображаются в один и тот же индекс, то второй ключ помещается в следующий доступный слот.

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

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

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

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

Хорошая хеш-функция должна обладать следующими свойствами.

1. Детерминированность. Для одних и тех же входных данных всегда должен возвращаться один и тот же результат. Таким образом можно обеспечить согласованность и предсказуемость.
2. Быстрое вычисление хеш-значения. Хеш-функция должна максимально быстро вычислять хеш для любого входного значения, чтобы обеспечить высокую общую производительность.
3. Равномерное распределение. Хеш-функция должна равномерно распределять ключи по массиву, то есть каждый индекс в массиве должен быть равновероятным. Это свойство поможет предотвратить кластеризацию значений в определенной области и избежать коллизий, снижающих общую эффективность хеш-таблицы и замедляющих поиск.
4. Низкая вероятность возникновения коллизий. Коллизии неизбежны, однако хорошая хеш-функция должна стремиться минимизировать их. Низкая частота коллизий способствует общей высокой эффективности хеш-таблицы и предотвращает снижение производительности, вызванное чрезмерно большим количеством коллизий.
5. Надежность. Хеш-функция должна обрабатывать широкий диапазон входных данных и для каждого входного значения создавать уникальный хеш. Это необходимо для того, чтобы хеш-таблица могла обрабатывать разные типы данных, не нанося ущерб производительности и эффективности.
6. Безопасность. В некоторых случаях важно, чтобы хеш-функция была безопасной и устойчивой к атакам. Например, в криптографии хеш-функции используются для проверки целостности данных и предотвращения их подделки. Безопасная хеш-функция должна предусматривать возможность противостояния таким атакам, как коллизии, атаки методом поиска прообразов и атаки на основе парадокса «день рождения» (birthday attacks).

Вот пример простой реализации хеш-функции:

def hash_function(key):
    return key % 10

Эта хеш-функция просто возвращает остаток от деления ключа key на размер массива (в данном случае 10). Вычисления выполняются очень быстро, но ключи могут распределяться неравномерно, особенно если в них наблюдаются некоторые закономерности.

Обратите внимание: описанные выше принципы составляют лишь самые основы. Хеширование — обширная область информатики, в которой продолжаются активные исследования и создаются все более сложные хеш-функции, стратегии разрешения коллизий и приемы их применения.

Прелесть хеш-таблиц в том, что они поддерживают связь между ключами и значениями, подобно словарям, и позволяют очень быстро (в идеале за постоянное время) выполнять операции поиска, добавления и удаления записей.

Об авторе

Cuantum Technologies — ведущая инновационная компания в сфере разработки программного обеспечения и образования, уделяющая особое внимание использованию возможностей искусственного интеллекта и передовых технологий. Специализируется на веб-приложениях и написании литературы по программированию и искусственному интеллекту. В ассортимент продуктов входят CuantumAI — инновационное SaaS — и множество книг, посвященных Python, NLP, PHP, JavaScript и многому другому.

Более подробно с книгой можно ознакомиться на сайте издательства:

» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Алгоритмы

P.S Обращаем ваше внимание на то, что у нас на сайте проходит распродажа.