Через десять постов мы подошли к тому моменту, когда, следуя шаблону, этот пост должен называться «CS101.0»! Однако, поскольку эта серия недостаточно глубока, а мои знания недостаточны для написания курса CS 101, мы назовем его CS 100.9.1. Не думайте, что это означает, что содержание здесь в любом случае на порядок менее важно, чем то, что мы рассмотрели до сих пор. На самом деле, хеш-таблицы — чрезвычайно фундаментальные структуры данных, и, вероятно, их следовало бы рассмотреть ранее в этой серии статей. Видите, я НИЧЕГО не знаю?! (Кроме того, обратите внимание, что я выбрал 100.9.1 вместо 100.91, отражая способ выпуска версий программного обеспечения. Кто-нибудь может сказать МЕТА?!)

Хорошо, к хеш-таблицам. Вы, вероятно, знакомы с любой реализацией хэш-таблиц, которую реализует выбранный вами язык: словари в Python, хэши в Ruby, объекты в JavaScript и т. д. Давайте возьмем соглашение об именах Python в качестве примера, поскольку оно является наиболее показательным. Хеш-таблица — это просто словарь. Когда вы думаете о том, что такое словарь на самом деле, это список пар ключ-значение, где поиск ключа сопоставляется с конкретным значением. Это может быть особенно полезно при решении задач, где на каждом шагу необходимо знать множество фрагментов информации, возможно, даже в некоторых задачах, для которых вы могли бы использовать массив (или несколько массивов). При правильном использовании хеш-таблицы могут значительно сократить временную сложность различных функций и сделать код более понятным.

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

Проблема с добавлением ключей в хеш-таблицу заключается в том, что ключи могут быть любыми. В массивы просто добавлять элементы и проверять, есть ли элементы; они хранятся в целочисленном индексе, и мы можем проверить наличие элемента по этому индексу. Хэш-ключи не обязательно являются целыми числами, поэтому нам нужен способ их стандартизации и сопоставления с согласованным набором возможных индексов. Здесь на помощь приходит хеширование. Хеш-функция берет определенный ключ и преобразует его в представление, которое можно сохранить в таблице. Хеш-функции должны всегда сопоставлять один и тот же ключ с одним и тем же местом, и они должны гарантировать, что все одинаковые ключи сопоставляются с одним и тем же местом (другими словами, 9.0, число с плавающей запятой, и 9, целое число, должны сопоставляться с одним и тем же местом в памяти). ). Проблема здесь в том, что при создании хеш-таблицы мы не всегда знаем, какие ключи и типы ключей нам нужно будет хранить. Более того, хеш-таблицы не являются структурами данных, эффективно использующими память, и могут быстро стать громоздкими, если мы выделим много места для сопоставления ключей. Борьба с хеш-таблицами заключается в поиске баланса между выделением слишком большого пространства и обеспечением того, чтобы уникальные ключи сопоставлялись с уникальными местоположениями. Когда два разных ключа сопоставляются с одним и тем же местом, это называется «коллизией» и должно обрабатываться хеш-функцией. Таким образом, это основная проблема хеш-функций: сопоставлять ключи как можно большему количеству различных местоположений, не занимая при этом лишней памяти, минимизировать коллизии и, когда они все же происходят, обрабатывать их максимально эффективно.

Возвращаясь к нашему примеру со словарем Python, хэш-функция словаря Python работает, беря 32-битное двоичное представление каждого ключа, сопоставляя его с последними тремя битами в этом ключе, и, если в этом месте происходит коллизия, вводя более ранние биты до тех пор, пока найден пустой слот. Когда 2/3 слотов в таблице заняты, размер таблицы изменяется (в 4 раза для таблицы длиной ‹50 000 записей, в 2 раза для таблицы >50 000). Однако это не самый распространенный способ обработки коллизий. Гораздо более типичным является использование «цепочки», при которой ключ сопоставляется с местоположением, и если там возникает конфликт, в этом месте создается связанный список, где каждый элемент в списке указывает на следующий ключ, который отображается на это место. В любом случае, суть в том, что хеш-таблицы эффективны именно потому, что мы можем писать хеш-функции, которые оптимизируют эффективность использования памяти при минимизации количества коллизий, создавая ситуацию, когда в среднем запись в таблице занимает не более 1–2 коллизии в глубину, и пространство, необходимое для этого, ненамного превышает количество элементов в списке. На самом деле, при правильном использовании хеш-таблица с хорошей хеш-функцией может найти заданный ключ и его значение, вставить ключ и удалить ключ, и все это в среднем за время O(1).

Важно понимать, что при хешировании с цепочкой, в худшем случае, и действительно, это справедливо для всех схем хэширования: время поиска, вставки и удаления будет O(n). Это связано с тем, что в худшем случае все элементы будут хэшированы в одно и то же место, и у нас останется список элементов n-длины. На практике мы можем сделать это невероятно маловероятным, и способ сделать это — одна из самых распространенных и до сих пор не обсуждавшихся алгоритмических стратегий в CS: рандомизация. Идея состоит в том, что при хешировании n ключей каждый ключ сопоставляется со случайным местоположением, и, таким образом, каждый ключ с одинаковой вероятностью может быть сопоставлен с любым местоположением. На практике это предположение не выполняется по разным причинам, но не беспокойтесь об этом и примите его за правду. Если это так, то предположим, что у нас есть n ключей и таблица длины m, ожидаемая длина каждой цепочки равна n/m, поскольку для каждого слота в таблице каждый ключ имеет шанс хеширования 1/m. , и есть n ключей. Ожидаемая длина цепи называется «коэффициентом нагрузки» в таблице. Если ключей в два раза больше, чем слотов в таблице, коэффициент загрузки будет равен двум. Если n равно 10, умноженному на m, коэффициент загрузки будет равен 10 и так далее. Это не важно. Что важно, так это то, что это константы, поэтому стоимость выполнения действия над таблицей всегда будет O(1+n/m) и, следовательно, будет равна постоянный.

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

h(k) = [(ak + b) mod p] mod m

Очевидно, что h(k) — это хеш-функция для конкретного ключа. p — это простое число, большее, чем множество возможных ключей, которые вы хешируете, поэтому, например, если вы составляете таблицу костей человеческого тела, p — это простое число >206. a и b — случайные числа от 0 до p. На практике эта функция создает ситуацию, когда вероятность хэширования двух неравных ключей в одно и то же место в худшем случае составляет 1/m, что означает, что наш теоретический идеал по существу соблюдается.

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

Я оставлю вас сегодня с некоторыми мудрыми словами от докладчика на PyCon 2010 по имени Брэндон Крейг Роудс.

«Пусть ваши хэши будут уникальными, ваши хеш-таблицы никогда не будут заполнены, и пусть ваши ключи редко будут конфликтовать»

Спасибо за чтение! До следующего раза.