Задача спроектируйте и реализуйте хэш-таблицу


Оглавление (нажмите, чтобы открыть):

Задача: спроектируйте и реализуйте хэш-таблицу

Один из наиболее эффективных способов реализации словаря — хеш-таблица. Среднее время поиска элемента в ней есть O (1), время для наихудшего случая — O ( n ). Прекрасное изложение хеширования можно найти в работах Кормена[1990] и Кнута[1998].

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


Теория. Открытое Хеширование

Хеш-таблица — это обычный массив с необычной адресацией, задаваемой хеш-функцией.

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

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

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

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

Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай — когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция. Здесь мы рассмотрим лишь несколько из возможных подходов. При иллюстрации методов предполагается, что unsigned char располагается в 8 битах, unsigned short int — в 16, unsigned long int — в 32.

  • Деление ( размер таблицы hashTableSize — простое число ). Этот метод использован в последнем примере. Хеширующее значение hashValue , изменяющееся от 0 до ( hashTableSize — 1 ), равно остатку от деления ключа на размер хеш-таблицы. Вот как это может выглядеть: Для успеха этого метода очень важен выбор подходящего значения hashTableSize . Если, например, hashTableSize равняется двум, то для четных ключей хеш-значения будут четными, для нечетных — нечетными. Ясно, что это нежелательно — ведь если все ключи окажутся четными, они попадут в один элемент таблицы. Аналогично, если все ключи окажутся четными, то hashTableSize , равное степени двух, попросту возьмет часть битов Key в качестве индекса. Чтобы получить более случайное распределение ключей, в качестве hashTableSize нужно брать простое число, не слишком близкое к степени двух.
  • Мультипликативный метод ( размер таблицы hashTableSize есть степень 2 n ). Значение key умножается на константу, затем от результата берется n бит. В качестве такой константы Кнут рекомендует золотое сечение ( sqrt (5) — 1)/2 = 0.6180339887499. Пусть, например, мы работаем с таблицей из hashTableSize=32(2 5 ) элементов, хэширование производится байтами(8 бит, unsigned char). Тогда необходимый множитель: 2 8 * sqrt (5) — 1)/2 = 158.

Далее, умножая 8-битовый ключ на 158, будем получать некоторое 16-битное число. Для таблицы длиной 2 5 в качестве хеширующего значения берем 5 старших битов младшего слова, содержащего такое произведение. Вот как можно реализовать этот метод: Пусть, например, размер таблицы hashTableSize равен 1024 (2 10 ). Тогда нам достаточен 16-битный индекс и величине сдвига S будет присвоено значение 16 — 10 = 6. В итоге получаем:

  • Аддитивный метод для строк переменной длины (размер таблицы равен 256) . Для строк переменной длины вполне разумные результаты дает сложение по модулю 256. В этом случае результат hashValue заключен между 0 и 255.
  • Исключающее ИЛИ для строк переменной длины ( размер таблицы равен 256 ). Этот метод аналогичен аддитивному, но успешно различает схожие слова и анаграммы (аддитивный метод даст одно значение для XY и YX). Метод, как легко догадаться, заключается в том, что к элементам строки последовательно применяется операция «исключающее или». В нижеследующем алгоритме добавляется случайная компонента, чтобы еще улучшить результат. Здесь Rand8 — таблица из 256 восьмибитовых случайных чисел. Их точный порядок не критичен. Корни этого метода лежат в криптографии; он оказался вполне эффективным.
  • Исключающее ИЛИ для строк переменной длины ( размер таблицы ). Если мы хешируем строку дважды, мы получим хеш-значение для таблицы любой длины до 65536. Когда строка хешируется во второй раз, к первому символу прибавляется 1. Получаемые два 8-битовых числа объединяются в одно 16-битовое.

  • Размер хеш-таблицы должен быть достаточно большим, чтобы в ней оставалось разумно большое число пустых мест. Как видно из таблицы 3.1, чем меньше таблица, тем больше среднее время поиска ключа в ней. Хеш-таблицу можно рассматривать как совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается. Пусть количество элементов равно n . Если размер таблицы равен 1, то таблица вырождается в один список длины n . Если размер таблицы равен 2 и хеширование идеально, то нам придется иметь дело с двумя списками по n /100 элементов в каждом. Это сильно уменьшает длину списка, в котором нужно искать. Как мы видим в таблице 3.1, имеется значительная свободы в выборе длины таблицы.

    размервремяразмервремя
    18691289
    24322566
    42145124
    810610244
    165420483
    322840963
    641581923
    Таблица 3.1: Зависимость среднего времени поиска (µs) от hashTableSize. Сортируются 4096 элементов
    Реализация В реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. Для работы программы следует также определить hashTableSize и отвести место под hashTable . В хеш-функции hash использован метод деления. Функция insertNode отводит память под новый узел и вставляет его в таблицу. Функция deleteNode удаляет узел и освобождает память, где он располагался. Функция findNode ищет в таблице заданный ключ.


    Метод закрытой адресации.

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

    Закрытые хеш-таблицы особенно эффективны, когда максимальные размеры входящего набора данных уже известены. Было доказано, что, когда закрытая таблица заполняется более чем на 50 процентов, ее эффективность значительно ухудшается (см. Структуры Данных, и Программируйте Проект на C, Робертом Крус, Брюсом Леунг, и Clovis Tondo, Prentice Холл, 1991).

    Закрытые таблицы обычно используются для быстродействующего макетирования (они просты для программирования и быстры) и там, где быстрый доступ (нет связаного списка) приоритетен, а память легко доступна.

    Пусть нам необходимо представлять множества элементов типа T, причем число элементов заведомо меньше n. Выберем некоторую функцию h, определенную на значениях типа T и принимающую значения 0..(n-1). Было бы хорошо, чтобы эта функция принимала на элементах будущего множества по возможности более разнообразные значения. Худший случай — это когда ее значения на всех элементах хранимого множества одинаковы. Эту функцию будем называть хеш-функцией.

    Введем два массива

    (мы позволяем себе писать n-1 в качестве границы в определении типа, хотя в паскале это не разрешается). В этих массивах будут храниться элементы множества: оно равно множеству всех val [i] для тех i, для которых used [i], причем все эти val [i] различ ны. По возможности мы будем хранить элемент t на месте h(t), считая это место «исконным» для элемента t. Однако может слу читься так, что новый элемент, который мы хотим добавить, пре тендует на уже занятое место (для которого used истинно). В этом случае мы отыщем ближайшее справа свободное место и запишем эле мент туда. («Справа» значит «в сторону увеличения индексов»; дойдя до края, мы перескакиваем в начало.) По предположению, число элементов всегда меньше n, так что пустые места гарантиро ванно будут.

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

    Благодаря этому проверка принадлежности заданного элемента t осуществляется легко: встав на h(t), двигаемся направо, пока не дойдем до пустого места или до элемента t. В первом случае элемент t отсутствует в множестве, во втором присутствует. Если элемент отсутствует, то его можно добавить на найденное пустое место. Если присутствует, то можно его удалить (положив used = false).

    Есть одна проблема:

    Дело в том, что при удалении требуемое свойство ‘отсутствия пустот’ может нарушиться. Поэтому будем делать так. Создав дыру, будем двигаться направо, пока не натолкнемся на еще одно пустое место (тогда на этом можно успокоиться) или на элемент, стоящий не на исконном месте. Во втором случае посмотрим, не нужно ли этот элемент поставить на место дыры. Если нет, то продолжаем поиск, если да, то затыкаем им старую дыру. При этом образуется новая дыра, с которой делаем все то же самое.

    Здесь есть функции на Паскале, реализующие проверку принадлежности, добавление и удаление элементов в таких таблицах.

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

    Хэш таблица

    17.11.2010, 19:12

    Хэш таблица
    Создать хэш-таблицу, занести в неё значения строк вида «Элемент X», где X – значение элемента.

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

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

    Реализовать структуру данных «хэш-таблица»
    1. Реализовать структуру данных «хэш-таблица», реализовав методы добавления, удаления и поиска.

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

    Хэш-таблицы: теория и практика

    Оригинал: Hash Tables-Theory and Practice
    Автор: Mihalis Tsoukalos
    Дата публикации: 12 октября 2015 г.
    Перевод: A.Панин
    Дата перевода: 13 октября 2015 г.

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

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

    Постановка задачи

    Задача, которую я буду рассматривать в качестве примера в рамках данной статьи, заключается в установлении количества слов из одного текстового файла, присутствующих в другом текстовом файле. Все программы из данной статьи будут использовать один и тот же текстовый файл для заполнения хэш-таблицы (этот текстовый файл будет содержать текст книги «Гордость и предубеждение»). Другой текстовый файл (содержащий текст книги «Приключения Тома Сойера») будет использоваться для тестирования производительности хэш-таблицы. Вы можете загрузить оба текстовых файла с ресурса Project Gutenberg.

    В следующем выводе приводится информация о количестве слов в каждом из упомянутых файлов:

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

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

    После создания хэш-таблицы с данными из первого файла (с именем INPUT) данные из второго файла (с именем CHECK) будут использоваться для тестирования хэш-таблицы. Именно таким образом хэш-таблицы чаще всего используются на практике.

    Теоретическая информация

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

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

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

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

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

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

    В хэш-таблице с «корректным» количеством корзин средняя цена каждой операции поиска значения не зависит от количества элементов таблицы.

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

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

    Хэш-таблицы также имеют некоторые недостатки:

    Они не предназначены для хранения отсортированных данных. Использование хэш-таблицы для сортировки данных не является продуктивным.

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


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

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

    Хэш-таблицы работают достаточно неэффективно при наличии множества коллизий.

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

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

    Рисунок 1. Простая хэш-таблица

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

    Не следует создавать слишком большое количество корзин; следует создавать ровно столько корзин, сколько требуется.

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

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

    Каждая корзина должна содержать одно и то же количество ключей или, по крайней мере, их сопоставимые количества (это очень желательное свойство).

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

    Добавление, удаление и поиск элементов

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

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

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

    Реализация на языке программирования C

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

    В Листинге 1 показан исходный код приложения на языке C из файла ht1.c.

    Более удачная реализация хэш-таблицы на языке программирования C

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

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

    Тестирование производительности

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

    Все программы компилируются с помощью следующей команды:

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

    На Рисунке 2 представлен график времени исполнения программы на основе исходного кода из файла ht1.c с четырьмя различными значениями константы TABLESIZE. Проблема реализации хэш-таблицы из файла ht1.c заключается в том, что производительность хэш-таблицы с 101 корзиной практически равна производительности хэш-таблицы с 1001 корзиной!

    Рисунок 2. Время исполнения программы на основе исходного кода из файла ht1.c при использовании четырех различных значений константы TABLESIZE

    А это результаты исполнения программы на основе исходного кода из файла ht2.c:

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

    Рисунок 3. График времени исполнения программы на основе исходного кода из файла ht2.c при использовании пяти различных значений константы TABLESIZE

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

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

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

    Рисунок 4. Количество ключей в каждой корзине двух хэш-таблиц с различным количеством корзин

    Заключение

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

    Хеш-таблица.

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

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

    Предположим, имеется товарная накладная с информацией о датах и городах (когда и куда отправляются товары). Определенному товару соответствует его числовой код в диапазоне от 000000000 до 999999999:

    000000000 2020-03-10 Тула …… …… …… 000142426 000142427 2020-08-25 Орел …… …… …… 603603003 2020-05-14 Казань 603603004 …… …… …… 999999999 2026-09-01 Хабаровск

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

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

    В качестве последней можно взять, например следующую:

    Формальный параметр key это строка, состоящая из 10 символов, т. е. дата. Функция erase() удаляет из строки key 5 символов, после чего результат вида «месяц-число» присваивается переменной h, которая и будет индексом нового списка. Например, из ключа 2026-09-01, путем хеширования, получился хеш-код 09-01. Таким образом, размер накладной заметно сокращается, исчезают все пустые элементы.

    Но в некоторых местах возможно возникновения проблем следующего типа: пусть имеется два ключа: 2020-06-06 и 2025-06-06, тогда результат работы функции в двух случаях будет 06-06, следовательно, разные значения в хеш-таблицы попадут под один и тот же индекс. Такая ситуация называется коллизией. Коллизий следует избегать, выбирая «хорошую» хеш-функцию, и используя один из методов разрешения конфликтов: открытое (метод цепочек) или закрытое (открытая адресация) хеширование.

    Открытое хеширование.

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

    На рисунке изображены связанные списки со ссылающейся на них хеш-таблицей (ее размер = M). Первый столбец таблицы содержит хешированные значения ключей, второй – ссылки на списки. Количество последних ограничено лишь числом элементов исходного массива (он не показан, но предполагается). Состоят списки из трех (последний элемент подсписка – из двух) полей: & — адрес элемента списка, $ — данные, * — указатель (ссылка).

    Если в исходном массиве было всего N элементов (столько же будут содержать в совокупности и все списки), то средняя длина списков будет равна α=N/M, где M – число элементов хеш-таблицы, α – коэффициент заполнения хеш-таблицы. Предположив, например, что в списке на рисунке выше M=5 (заклеив 4-ую по счету строку), получим среднее число списков α=2.

    Чтобы увеличить скорость работы операций поиска, вставки и удаления нужно, зная N, подобрать M примерно равное ему, т. к. тогда α будет равняться 1-ому или ≈1-ому, следовательно, можно рассчитывать на оптимальное время, в лучшем случае равное O(1). В худшем случае все N элементов окажутся в одном списке, и тогда, например, операция нахождения элемента (в худшем случае) потребует O(N) времени.

    Закрытое хеширование.

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

    Сам процесс заполнения хеш-таблицы с использованием алгоритма закрытого хеширования осуществляется следующим образом:

    1. имеется изначально пустая хеш-таблица T размера M, массив A размера N (M≥N) и хеш-функция h(), пригодная для обработки ключей массива A;
    2. элемент xi, ключ которого keyi, помещается в одну из ячеек хеш-таблицы, руководствуясь следующим правилом:


    a) если h(keyi) – номер свободной ячейки таблицы T, то в последнюю записывается xi;

    b) если h(keyi) – номер уже занятой ячейки таблицы T, то на занятость проверяется другая ячейка, если она свободна то xi заноситься в нее, иначе вновь проверяется другая ячейка, и так до тех пор, пока не найдется свободная или окажется, что все M ячеек таблицы заполнены.

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

    Рассмотрим метод закрытого хеширования на примере построения хеш-таблицы. Положим, имеется целочисленный массив A, состоящий из 9 элементов:

    A[13]=8, A[56]=4, A[79]=1, A[37]=5, A[41]=2, A[76]=9, A[51]=3, A[93]=9, A[30]=1

    Также есть хеш-таблица размера M=10, и хеш-функция h(key)=key % M (% – операция «остаток от деления»). Заполним хеш-таблицу элементами массив A: Для расстановки элементов использовалась выбранная формула. Подставив ключ, например первого элемента в нее получим: h(13) = 13 % 10 = 3, поэтому его номер в хеш-таблице 3. Последовательное добавление элементов приведет к возникновению коллизии при обработке элемента A[76]. Хеш-код его ключа 6, но в хеш-таблице ячейка с таким номером уже занята.

    Используя формулу линейного пробирования (тип последовательности проб) hi(key)=(h(key) + i) % M (i – число проверок, после первой проверки i=0), продолжим поиск свободной ячейки. Применим функцию при i=1: h1(76)=7; убедившись, что ячейка 7 занята, продолжаем поиск, увеличив i на 1: h2(76)=8. Ячейка 8 свободна, помещаем в нее элемент. Этот же метод используем и для всех остальных элементов.

    Хеш-таблица (hashtable) C#

    Опубликовано shwan в 16.03.2020

    Хеш-таблица (hashtable) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данных. Все данные хранятся в виде пар хеш-значения. Данная структура похожа на словарь (map), но имеет особенности такие как применение хеш-функции для увеличения скорости поиска. Принцип работы данной структуры схож с каталогом книг. Все книги разложены в алфавитном порядке, но не на одном стеллаже, а для каждой буквы выделен отдельный стеллаж, поэтому нам не нужно по порядку перебирать все книги, а можно подойти к нужному стеллажу и искать уже там. Давайте рассмотрим пример реализации хеш-таблицы на языке C#.

    Существуют два основных способа реализации хеш-таблиц:

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

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

    Доступ к элементам осуществляется по его ключу. Основные операции, которые могут выполняться с хеш-таблицей?

    • Insert — добавить новый элемент в хеш-таблицу
    • Delete — удалить элемент из хеш-таблицы по ключу
    • Search — получить значение по ключу

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

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

    Задача: спроектируйте и реализуйте хэш-таблицу

    [Tutorial] Полиномиальное хэширование + разбор интересных задач

    Здравствуйте! Этот пост написан для всех тех, кто хочет освоить полиномиальные хэши и научиться применять их в решении различных задач. Я кратко приведу теоретический материал, рассмотрю особенности реализации и разберу некоторые задачи, среди них:

    Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)

    Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))

    Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n) 2 )

    Нахождение количества подпалиндромов строки длины n за O(n·log(n))

    Количество подстрок строки длины n , являющихся циклическими сдвигами строки длины m за O((n + mlog(n))

    Количество суффиксов строки длины n , бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n)) (расширение — дублирование строки бесконечное число раз)

    Наибольший общий префикс двух строк длины n с обменом двух произвольных символов одной строки местами за O(n·log(n))

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

    Примечание 2. В задачах выше приведена оценка, когда поиск хэша осуществляется при помощи сортировки и бинарного поиска. Если у Вас есть своя хэш-таблица с открытым перемешиванием или цепочками переполнения, то Вы — счастливчик, смело заменяйте бинарный поиск хэша на поиск в Вашей хэш-таблице, но не вздумайте использовать std::unordered_set , так как на практике поиск в std::unordered_set проигрывает сортировке и бинарному поиску в связи с тем, что эта штука подчиняется стандарту C++ и обязана много чего гарантировать пользователю, что полезно при промышленной разработке и, зачастую, бесполезно в олимпиадном программировании, поэтому сортировка и бинарный поиск для несложных структур одерживают абсолютное первенство в C++ по скорости работы, если не тянуть что-то свое.

    Примечание 3. В тех случаях, когда сравнение элементов затратно (например, сравнение по хэшам за O(log(n)) ), то в худшем случае std::random_shuffle + std::sort всегда проигрывает std::stable_sort , так как std::stable_sort гарантирует минимальное число сравнений среди всех сортировок (основанных на сравнениях) для худшего случая.

    Решение перечисленных задач будет приведено ниже, исходники тоже.

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

    Среди минусов полиномиального хэширования: а) Слишком много операций остатка от деления, порой на грани TLE на больших задачах и б) на codeforces в программах на C++ зачастую маленькие гарантии от взлома из-за MinGW: std::random_device генерирует каждый раз одно и то же число, std::chrono::high_resolution_clock тикает в микросекундах вместо наносекунд. (Компилятор cygwin на windows лишен всех недостатков MinGW, в том числе и медленного ввода/вывода).

    Для того, чтобы не использовать медленную операцию взятия остатка от деления, можно взять два модуля m 1 = 2 31 — 1 и m 2 = 2 64 .

    Тогда для взятия остатка от деления по модулю m 2 необходимо проводить вычисления в беззнаковом 64-битном типе, например, в типе unsigned long long в C++, т.к. во многих языках программирования гарантируется, что вычисления в этом типе данных будут проводиться по модулю 2 64 .

    Для взятия остатка от деления по модулю 2 31 — 1 = 2147483647 для положительных чисел x до (mod — 1) 2 + mod — 1 (результат умножения двух остатков и одного сложения) можно брать смещенный остаток следующим образом:

    В случае сложения и вычитания по модулю m 1 двух остатков можно обойтись обычным тернарным оператором.

    Достаточно делать побитовое ИЛИ для значений текущего времени и адреса в памяти, полученного от менеджера кучи:

    Что такое полиномиальный хэш?

    Хэш-функция должна сопоставлять некоторому объекту некоторое число (его хэш) и обладать следующими свойствами:

    Если два объекта совпадают, то их хэши равны.

    Если два хэша равны, то объекты совпадают с большой вероятностью.

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

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

    Рассмотрим последовательность <a 0, a 1, . a n — 1> . Под полиномиальным хэшем слева-направо для этой последовательности будем иметь в виду результат вычисления следующего выражения:

    Здесь p и m — точка (или основание) и модуль хэширования соответственно.

    Условия, которые мы наложим: , .

    Примечание. Если подумать об интерпретации выражения, то мы сопоставляем последовательности <a 0, a 1, . a n — 1> число длины n в системе счисления p и берем остаток от его деления на число m , или значение многочлена (n — 1) -й степени с коэффициентами a i в точке p по модулю m . О выборе p и m поговорим позже.

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

    Сравнение на равенство за O(1)

    Теперь ответим на вопрос, как сравнивать произвольные непрерывные подотрезки последовательности за O(1) ? Покажем, что для их сравнения достаточно посчитать полиномиальный хэш на каждом префиксе исходной последовательности <a 0, a 1, . a n — 1> .

    Определим полиномиальный хэш на префиксе как:

    Кратко обозначим как и будем иметь в виду, что итоговое значение берется по модулю m . Тогда:

    Полиномиальный хэш на каждом префиксе можно находить за O(n) , используя рекуррентные соотношения:

    Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len , на равенство:

    Рассмотрим разности и . Не трудно видеть, что:

    Домножим 1-е уравнение на p j , а 2-е на p i . Получим:


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

    Таким образом, чтобы определить, совпали ли искомые подотрезки, необходимо проверить выполнение следующего равенства:

    Одно такое сравнение можно выполнять за O(1) , предподсчитав степени p по модулю. С учетом модуля m , имеем:

    Проблема: сравнение одной строки зависит от параметров другой строки (от j ).

    Первое решение данной проблемы (предложил veschii_nevstrui) основывается на домножении первого уравнения на pi , а второго на pj . Тогда получим:

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

    Для реализации этого необходимо найти обратный элемент для p по модулю m . Из условия gcd(p, m) = 1 обратный элемент всегда существует. Для этого необходимо вычислить значение функции Эйлера для выбранного модуля φ(m) и возвести p в степень φ(m) — 1 . Если предподсчитать степени обратного элемента по выбранному модулю, то сравнение можно выполнять за O(1) .

    Второе решение данной проблемы основывается на знании максимальной длины сравниваемых строк. Обозначим максимальную длину сравниваемых строк как . Домножим 1-е уравнение на p в степени mxPowilen + 1 , а 2-е на p в степени mxPowjlen + 1 . Тогда:

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

    Этот подход позволяет сравнивать одну подстроку длины len со всеми подстроками длины len на равенство, в том числе, и подстроками другой строки, так как выражение для подстроки длины len , начинающейся в позиции i , зависит только от параметров подстроки i , len и константы mxPow , а не от параметров другой подстроки.

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

    Кратко обозначим как и будем иметь в виду, что итоговое значение берется по модулю m . Тогда:

    Полиномиальный хэш на каждом префиксе можно находить за O(n) , используя рекуррентные соотношения:

    Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len , на равенство:

    Рассмотрим выражение и . Не трудно видеть, что:

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

    Таким образом, чтобы определить, совпали ли искомые подотрезки, необходимо проверить выполнение следующего равенства:

    Одно такое сравнение можно выполнять за O(1) , предподсчитав степени p по модулю m .

    Сравнение на больше / меньше за O(log(n))

    Рассмотрим две подстроки возможно разных строк длин len1 и len2 , (len1 ≤ len2) , начинающиеся в позициях i и j соответственно. Заметим, что отношение больше / меньше определяется первым несовпадающим символом в этих подстроках, а до позиции этого символа строки совпадают. Таким образом, необходимо найти позицию первого несовпадающего символа методом бинарного поиска, а затем сравнить найденные символы. Благодаря сравнению подстрок на равенство за O(1) , можно решить задачу сравнения подстрок на больше / меньше за O(log(len1)) :

    Минимизация вероятности коллизии

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

    Отсюда очевидно, что m нужно брать значительно больше, чем n 2 . Тогда, аппроксимируя экспоненту рядом Тейлора, получаем вероятность коллизии на одном тесте:

    Если мы рассмотрим задачу о поиске вхождений всех циклических сдвигов одной строки в другую строку длин до 10 5 , то мы можем получить 10 15 сравнений строк.

    Тогда, если мы возьмем простой модуль порядка 10 9 , то мы не пройдем ни один из максимальных тестов.

    Если мы возьмем модуль порядка 10 18 , то вероятность коллизии на одном тесте ≈ 0.001 . Если максимальных тестов 100 , то вероятность коллизии в одном из тестов ≈ 0.1 , то есть 10% .

    Если мы возьмем модуль порядка 10 27 , то на 100 максимальных тестах вероятность коллизии равна ≈ 10 — 10 .

    Вывод: чем больше модуль — тем больше вероятность пройти тест. Эта вероятность не учитывает взломы.

    Двойной полиномиальный хэш

    Разумеется, в реальных программах мы не можем брать модули порядка 10 27 . Как быть? На помощь приходит китайская теорема об остатках. Если мы возьмем два взаимно простых модуля m 1 и m 2 , то кольцо остатков по модулю m = mm 2 эквивалентно произведению колец по модулям m 1 и m 2 , т.е. между ними существует взаимно однозначное соответствие, основанное на идемпотентах кольца вычетов по модулю m . Иными словами, если вычислять по модулю m 1 и по модулю m 2 , а затем сравнивать два искомых подотрезка по и одновременно, то это эквивалентно сравнению полиномиальным хэшем по модулю m . Аналогично, можно брать три взаимно простых модуля m 1 , m 2 , m 3 .

    Особенности реализации

    Итак, мы подошли к реализации описанного выше. Цель — минимум взятий остатка от деления, т.е. получить два умножения в 64-битном типе и одно взятие остатка от деления в 64-битном типе на одно вычисление двойного полиномиального хэша, при этом получить хэш по модулю порядка 10^27 и защитить код от взлома на codeforces.

    Выбор модулей. Выгодно использовать двойной полиномиальный хэш по модулям m1 = 1000000123 и m2 = 2^64 . Если Вам не нравится такой выбор m1 , можете выбрать 1000000321 , главное выбрать такое простое число, чтобы разность двух остатков лежала в пределах знакового 32-битного типа (int). Простое число брать удобнее, так как автоматически обеспечиваются условия gcd(m1, m2) = 1 и gcd(m1, p) = 1 . Выбор в качестве m2 = 2^64 не случаен. Стандарт C++ гарантирует, что все вычисления в unsigned long long выполняются по модулю 2^64 автоматически. Отдельно модуль 2^64 брать нельзя, так как существует анти-хэш тест, который не зависит от выбора точки хэширования p . Модуль m1 необходимо задать как константу для ускорения взятия модуля (компилятор (не MinGW) оптимизирует, заменяя умножением и побитовым сдвигом).

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

    Выбор основания. В качестве основания p достаточно взять любое нечетное число, удовлетворяющее условию max(a[i]) . (нечетное, потому что тогда gcd(p, 2^64) = 1 ). Если Вас могут взломать, то необходимо генерировать p случайным образом с каждым новым запуском программы, причем генерация при помощи std::srand(std::time(0)) и std::rand() не подходит, так как std::time(0) тикает очень медленно, а std::rand() не обеспечивает достаточной равномерности. Если компилятор НЕ MinGW (к сожалению, на codeforces установлен MinGW), то можно использовать std::random_device , std::mt19937 , std::uniform_int_distribution (в cygwin на windows и gnu gcc на linux данный набор обеспечивает почти абсолютную случайность). Если не повезло и Вас посадили на MinGW, то ничего не остается, как std::random_device заменить на std::chrono::high_resolution_clock и надеяться на лучшее (или есть способ достать какой-нибудь счетчик из процессора?). На MinGW этот таймер тикает в микросекундах, на cygwin и gnu gcc в наносекундах.

    Гарантии от взлома. Нечетных чисел до модуля порядка 10^9 тоже порядка 10^9 . Взломщику необходимо будет сгенерировать для каждого нечетного числа анти-хэш тест так, чтобы была коллизия в пространстве до 10^27 , скомпоновать все тесты в один большой тест и сломать Вас. Это если использовать не MinGW на Windows. На MinGW таймер тикает, как уже говорилось, в микросекундах. Зная время запуска решения на сервере с точностью до секунд, можно для каждой из 10^6 микросекунд вычислить, какое случайное p сгенерировалось, и тогда вариантов в 1000 раз меньше. Если 10^9 это какая-то космическая величина, то 10^6 уже кажется не такой безопасной. При использовании std::time(0) всего 10^3 вариантов (миллисекунды) — можно ломать. В комментариях я видел, что гроссмейстеры умеют ломать полиномиальный хэш до 10^36 .

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

    UPD: Для ускорения программ можно быстро вычислять остатки от делений на модули 2 31 — 1 и 2 61 — 1 . Основная сложность заключается в умножении. Чтобы понять принцип, посмотрите следующий пост от dacin21 в параграфе Larger modulo и его комментарий с объяснениями.

    Задача 1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)

    Дано: Две строки S и T длин до 50000 . Вывести все позиции вхождения строки T в строку S . Индексация с нуля.

    Пример: Ввод S = «ababbababa» , T = «aba» , вывод: 0 5 7 .

    Посчитаем полиномиальный хэш на префиксах строк S и T . Будем идти вдоль строки S , сравнивая полиномиальный хэш текущей подстроки со всей строкой T . При совпадении хэшей выводим текущую позицию. Асимптотика: O(n) по времени и памяти. Исходный код.

    Задача 2. Поиск наибольшей общей подстроки двух строк длин n и m (nm) за O((n + m·log(n))·log(m)) и O(n·log(m))

    Дано: Длина строк N и две строки A и B длины до 100000 . Вывести длину наибольшей общей подстроки.

    Пример: Ввод: N = 28 , A = «VOTEFORTHEGREATALBANIAFORYOU» , B = «CHOOSETHEGREATALBANIANFUTURE» , вывод: THEGREATALBANIA

    Первым делом посчитаем полиномиальный хэш на префиксах строк A и B . Пусть мы нашли наибольшую общую подстроку длины len , начинающуюся в позиции pos любой из строк. Тогда общей подстрокой будет также и любая подстрока длин len-1, len-2, . 1 , начинающаяся в позиции pos , а len+1 уже не будет являться общей подстрокой. Видно, что выполняются условия бинарного поиска. Инициализация бинарного поиска: low = 0 , high = N+1 . На каждой итерации поиска будем складывать все хэши подстрок длины mid строки A в вектор, сортировать его, а дальше проходить по хэшам подстрок длины mid строки B и искать их среди отсортированных хэшей строки A . Асимптотика решения по времени O(n log(n)^2) , по памяти O(n) . Исходный код.

    Решение для 10^6 за O(n log(n)^2) с сжатием символов Решение для 10^6 за O(n log(n)) с хэш-таблицей с открытой адресацией

    Задача 3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))

    Дано: Строка S длины до 10^5 . Вывести минимальный лексикографически сдвиг строки A .

    Пример: Ввод: «program» , Вывод: «amprogr»

    В этой задаче необходимо написать сравнение двух подстрок методом бинарного поиска, описанным выше. Продублируем строку S и посчитаем полиномиальный хэш на префиксе. Каждый циклический сдвиг будем представлять в виде числа (начальной позиции). Сложим в вектор все позиции, а дальше применим линейный алгоритм нахождения минимума в массиве, используя оператор сравнения подстрок. Асимптотика: O(n log(n)) по времени и O(n) по памяти. Исходный код.

    Задача 4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n) 2 )

    Дано: Строка S длины до 10^5 . Вывести номер позиции исходного слова в отсортированном списке циклических сдвигов. Если таких позиций несколько, то следует вывести позицию с наименьшим номером. Во второй строке вывести последний столбец таблицы циклических сдвигов.

    Пример: Ввод: «abraka» , Вывод: «2 karaab»

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

    Не хотите строить суффиксный массив? Я тоже. Но когда-то все-таки нужно будет его построить, а пока продублируем строку S и посчитаем полиномиальный хэш на префиксе. Каждый циклический сдвиг будем представлять в виде числа (начальной позиции). Сложим в вектор все позиции, а дальше применим устойчивую сортировку слиянием, используя оператор сравнения подстрок. Асимптотика: O(n log(n)^2) по времени и O(n) по памяти.

    Победила сортировка слиянием. Если кто-нибудь сдаст построением суффиксного массива, сообщите Ваш результат.

    Задача 5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))

    Дано: Строка S длины до 10^5 . Вывести количество подпалиндромов строки.


    Пример: Ввод: «ABACABADABACABA» , Вывод: 32

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

    Пусть строка S — исходная, а строка T — развернутая. Тогда необходимо сравнивать хэши:

    S[i. i+len-1] и T[j. j+len-1] , где j = n — i + 1 .

    Затем будем строить палиндромы четной длины. В этом случае нужно сравнивать хэши:

    S[i+1. i+len] и T[j. j+len-1] , где j = n — i + 1 .

    Асимптотика решения: O(nlog(n)) по времени и O(n) по памяти. Исходный код для 10^5 Исходный код для 10^6

    Задача 6. Количество подстрок строки длины n , являющихся циклическими сдвигами строки длины m за O((n + mlog(n))

    Дано: Заданы две строки S и T длины до 10^5 . Необходимо определить, сколько подстрок строки S являются циклическими сдвигами строки T .

    Пример: Ввод: S = «aAaa8aaAa» , T=»aAa» , Вывод: 4

    Запомним исходную длину строки T и продублируем строку 2 раза. Пусть n — исходная длина. Построим полиномиальный хэш на префиксах строк S и T . Выпишем хэши всех подстрок длины n строки T и отсортируем. Теперь задача свелась к тому, чтобы поискать каждую подстроку длины n строки S среди выписанных хэшей строки T . Это можно сделать за O(n log(n)) по времени и O(n) по памяти. Исходный код.

    Задача 7. Количество суффиксов строки длины n , бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n))

    Дано: Строка S длины до 10^5 . Бесконечным расширением строки назовем строку, полученную выписыванием исходной строки бесконечное число раз. Например, бесконечное расширение строки «abс» равно «abcabcabcabcabc. «. Необходимо ответить на вопрос, сколько суффиксов исходной строки имеют такое же бесконечное расширение, какое и строка S .

    Пример: На входе: S = «qqqq» , на выходе 4 .

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

    Пусть есть префикс S[0. m) длины m и префикс S[0. n) длины n , где n >= m . Рассмотрим расширение длины n*m . Это будет означать, что мы префикс S[0..m) запишем n раз подряд, а префикс S[0..n) — m раз подряд:

    S[0. m)* = (1+p^m+p^(2m)+p^(3m)+p^((n-1)m))(S[0] + S[1] * p + S[2] * p^2 + . + S[m-1] * p^(m-1)))

    S[0. n)* = (1+p^n+p^(2n)+p^(3n)+p^((m-1)n))(S[0] + S[1] * p + S[2] * p^2 + . + S[n-1] * p^(n-1)))

    Хэш на префиксе вычислять мы уже умеем, осталось решить подзадачу вычисления следующей суммы:

    Ответ sum(a, k) = (a^k-1) / (a — 1) = (a^k — 1) * inverse(a-1, mod) — неверный, так как у четных чисел нет обратных в кольце по модулю 2^64 .

    Пусть k — четное, например, k = 8 . Тогда:

    sum(a,8) = 1+a+a^2+a^3+a^4+a^5+a^6+a^7 = (1+a)*(1+a^2+a^4+a^6) = (1+a) * sum(a^2, 4)

    пусть k — нечетное, например, k = 7 . Тогда:

    sum(a,7) = 1+a+a^2+a^3+a^4+a^5+a^6 = 1 + a * (1+a+a^2+a^3+a^4+a^5) = 1 + a * sum(a, 6)

    Получили рекуррентные формулы, позволяющие вычислять значения sum(a, k) для любых a и k за O(log(k)) :

    sum(a, 2*k) = (1+a) * sum(a^2, k) и sum(a, 2*k+1) = 1 + a * sum(a, 2*k) .

    В случае простого же модуля предложенный способ вычисления суммы геометрической прогрессии быстрее в два раза, чем sum(a, k) = (a^k — 1) * inverse(a-1, mod) , так как второй способ вызывает функцию быстрого возведения в степень два раза. В случаях с хэшами ускорение в два раза может быть критично.

    Осталось только сравнить sum(p^m, n) * pref(m) с sum(p^n, m) * pref(n) . Асимптотика решения O(n log(n)) по времени и O(n) по памяти. Исходный код.

    Задача 8. Наибольший общий префикс двух строк длины n с обменом двух произвольных символов одной строки местами за O(n·log(n))

    Дано: Строки S и T длиной до 2*10^5 . Разрешается один раз обменять местами два произвольных символа строки S или не менять вовсе. Найти максимальную длину наибольшего общего префикса среди всех возможных замен.

    Пример: На входе: S = «aaabaaaaaa» и T = «aaaaaaaaab» , на выходе 10 .

    Заметим, что для улучшения результата нужно обязательно поменять местами элемент в позиции первого различия строк. После нахождения этой позиции пытаемся менять по очереди этот символ со всеми символами, находящимися после него и находить длину наибольшего общего префикса бинарным поиском. Как пересчитывать полиномиальный хэш на префиксе длины len после замены символов в позициях i и j ? Три случая:

    Отрезок [0, len) не содержит i : ответ pref(len)

    Отрезок [0, len) не содержит j : ответ pref(i) + a[j] * p ^ i + pref(len) — pref(i+1)

    Иначе: pref(i) + a[j] * p ^ i + pref(j) — pref(i+1) + a[i] * p ^ j + pref(len) — pref(j+1)

    Асимптотика: O(n log(n)) по времени и O(n) по памяти. Исходный код.

    На этом все. Надеюсь, этот пост поможет Вам активно применять хэширование и решать более сложные задачи. Буду рад любым комментариям, исправлениям и предложениям. В ближайших планах перевести этот пост на английский язык, поэтому нужны ссылки, где эти задачи можно сдать на английском языке. Возможно, к тому времени Вы внесете существенные корректировки и дополнения в этот пост. Ребята из Индии говорят, что пытались сидеть с гугл-переводчиком и переводить с русского языка посты про полиномиальный хэш и у них это плохо вышло. Делитесь другими задачами и, возможно, их решениями, а также решениями указанных задач не через хэши. Спасибо за внимание!

    Что такое хеш-таблицы и как они работают

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

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

    Простое представление хеш-таблиц

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

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

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

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

    Учтите, что хеш-функция должна иметь следующие свойства:

    • Всегда возвращать один и тот же адрес для одного и того же ключа;
    • Не обязательно возвращает разные адреса для разных ключей;
    • Использует все адресное пространство с одинаковой вероятностью;
    • Быстро вычислять адрес.

    Борьба с коллизиями (они же столкновения)

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

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

    Метод цепочек

    Этот метод часто называют открытым хешированием. Его суть проста — элементы с одинаковым хешем попадают в одну ячейку в виде связного списка.

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

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

    В C++ метод цепочек реализуется так:

    # Проверка ячейки и создание списка

    Открытая индексация (или закрытое хеширование)

    Второй распространенный метод — открытая индексация. Это значит, что пары ключ-значение хранятся непосредственно в хеш-таблице. А алгоритм вставки проверяет ячейки в некотором порядке, пока не будет найдена пустая ячейка. Порядок вычисляется на лету.

    Самая простая в реализации последовательность проб — линейное пробирование (или линейное исследование). Здесь все просто — в случае коллизии, следующие ячейки проверяются линейно, пока не будет найдена пустая ячейка.


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

    Метод линейного пробирования для открытой индексации на C++:

    # Проверка ячеек и вставка значения

    Самое главное

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

    2 примера денормализации для оптимизации базы данных

    Простые и быстрые варианты переноса ключей Redis на другой сервер.

    Разделение базы данных на несколько независимых баз

    Типы и способы применения репликации на примере MySQL

    Как решать типичные задачи с помощью NoSQL

    Основные понятия о шардинге и репликации

    Как строятся по-настоящему большие системы на основе MySQL

    Поиск по большому количеству текста

    Как делать перераспределение данных между серверами

    Разделение таблиц данных на разные узлы

    Быстрый подсчет уникальных значений за разные периоды времени

    Худшие практики при работе над растущими проектами

    Введение в кэширование данных на примере Memcache

    Примеры использования Lua в Nginx для решения стандартных задач

    Повышение скорости работы запросов с MySQL Handlersocket

    Что такое индексы в Mysql и как их использовать для оптимизации запросов

    Примеры использования колоночной базы данных Vertica

    Как построить мини CDN на основе распределенного Nginx кеша

    Работа приложения с несколькими бэкендами при помощи Nginx

    Правила и практика масштабирования Твиттера

    Архитектурные принципы высоконагруженных приложений

    Как и зачем используются очередей сообщений

    Что значит высокая нагрузка (highload) и что при этом делать?

    3 аспекта эффективного мониторинга для Web приложений

    Задача: спроектируйте и реализуйте хэш-таблицу

    Прежде чем задать вопрос, смотрите FAQ.
    Рекомендуем загрузить DRKB.

    Группа: Пользователи
    Сообщений: 318
    Пол: Мужской

    Задание. Реализовать метод открытого хеширования. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1->(((((Для преобразования текстовых ключей в числовые значения использовать суммирование кодов символов текстового ключа: код (End) = код (E) + код (n) + код (d). Преобразование числового кода ключа в значение индекса выполнить с помощью простейшей хеш-функции, которая берет остаток от целочисленного деления кода на размер хеш-таблицы делить надо на константу m))). В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка.
    Программа должна выполнять следующие действия:
    • добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений
    • поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений
    • вывод текущего состояния таблицы на экран
    • удаление заданного ключа из таблицы
    Алгоритм удаления:
    • вычислить хеш-функцию и организовать поиск удаляемого элемента в таблице
    • если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей
    • если удаляемый элемент найден в списке, то производится его удаление с изменением указателей
    После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии размерности таблицы на эффективность поиска.

    Все работает вроде верно, но когда сдавал преподу он мне сказал ввести ключ var а потом ввести ключ avr//и программа сразу вылетела. препод сказал что у мя чтото с процедурой добавления и проблема с указтелями. ни как не пойму что и как исправить..помогите пожалуйста.(

    Группа: Пользователи
    Сообщений: 318
    Пол: Мужской

    Разрешение коллизий

    Разрешение коллизий (англ. collision resolution) в хеш-таблице, задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.

    Содержание

    Разрешение коллизий с помощью цепочек [ править ]

    Каждая ячейка [math]i[/math] массива [math]H[/math] содержит указатель на начало списка всех элементов, хеш-код которых равен [math]i[/math] , либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.

    В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна [math]O(1)[/math] . Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за [math]O(n)[/math]

    Время работы поиска в наихудшем случае пропорционально длине списка, а если все [math]n[/math] ключей захешировались в одну и ту же ячейку (создав список длиной [math]n[/math] ) время поиска будет равно [math]\Theta(n)[/math] плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех [math]n[/math] элементов.

    Удаления элемента может быть выполнено за [math]O(1)[/math] , как и вставка, при использовании двухсвязного списка.

    Линейное разрешение коллизий [ править ]

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

    Стратегии поиска [ править ]

    При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+1, i+2, i+3[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.

    Выбираем шаг [math]q[/math] . При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+(1 \cdot q), i+(2 \cdot q), i+(3 \cdot q)[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент. По сути последовательный поиск — частный случай линейного, где [math]q=1[/math] .

    Шаг [math]q[/math] не фиксирован, а изменяется квадратично: [math]q = 1,4,9,16. [/math] . Соответственно при попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math] i+1, i+4, i+9[/math] и так далее, пока не найдём свободную ячейку.

    Проверка наличия элемента в таблице [ править ]

    Проверка осуществляется аналогично добавлению: мы проверяем ячейку [math]i[/math] и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.

    При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.

    Проблемы данных стратегий [ править ]

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

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

    Удаление элемента без пометок [ править ]

    Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на [math]q[/math] позиций назад. При этом:

    • если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)
    • в цепочке не должно оставаться «дырок», тогда любой элемент с данным хешем будет доступен из начала цепи


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

    Хеш-таблицу считаем зацикленной

    Утверждение (о времени работы):
    [math]\triangleright[/math]
    Заметим что указатель [math]j[/math] в каждой итерации перемещается вперёд на [math]q[/math] (с учётом рекурсивных вызовов [math]\mathrm[/math] ). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего — с учётом вызова [math]\mathrm[/math] собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
    [math]\triangleleft[/math]

    Вариант с зацикливанием мы не рассматриваем, поскольку если [math]q[/math] взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций

    Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.

    • В редактируемой цепи не остаётся дырок

    Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце [math]\mathrm[/math] (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.

    • Элементы, которые уже на своих местах, не должны быть сдвинуты.
    • В других цепочках не появятся дыры

    Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на [math]q[/math] позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.

    Двойное хеширование [ править ]

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

    Принцип двойного хеширования [ править ]

    При двойном хешировании используются две независимые хеш-функции [math] h_1(k) [/math] и [math] h_2(k) [/math] . Пусть [math] k [/math] — это наш ключ, [math] m [/math] — размер нашей таблицы, [math]n \bmod m [/math] — остаток от деления [math] n [/math] на [math] m [/math] , тогда сначала исследуется ячейка с адресом [math] h_1(k) [/math] , если она уже занята, то рассматривается [math] (h_1(k) + h_2(k)) \bmod m [/math] , затем [math] (h_1(k) + 2 \cdot h_2(k)) \bmod m [/math] и так далее. В общем случае идёт проверка последовательности ячеек [math] (h_1(k) + i \cdot h_2(k)) \bmod m [/math] где [math] i = (0, 1, \; . \;, m — 1) [/math]

    Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за [math]O(1)[/math] , в худшем — за [math]O(m)[/math] , что не отличается от обычного линейного разрешения коллизий. Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.

    [math]\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))\gt p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))[/math]

    Выбор хеш-функций [ править ]

    [math] h_1 [/math] может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, [math] h_2 [/math] должна возвращать значения:

    • не равные [math] 0 [/math]
    • независимые от [math] h_1 [/math]
    • взаимно простые с величиной хеш-таблицы

    Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а [math] h_2 [/math] возвращает натуральные числа, меньшие [math] m [/math] . Второй — размер таблицы является степенью двойки, а [math] h_2 [/math] возвращает нечетные значения.

    Например, если размер таблицы равен [math] m [/math] , то в качестве [math] h_2 [/math] можно использовать функцию вида [math] h_2(k) = k \bmod (m-1) + 1 [/math]

    Пример [ править ]

    Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

    [math] h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 [/math]

    [math] h_1(k) = k \bmod 13 [/math]

    [math] h_2(k) = 1 + k \bmod 11 [/math]

    Мы хотим вставить ключ 14. Изначально [math] i = 0 [/math] . Тогда [math] h(14,0) = (h_1(14) + 0\cdot h_2(14)) \bmod 13 = 1 [/math] . Но ячейка с индексом 1 занята, поэтому увеличиваем [math] i [/math] на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При [math] i = 2 [/math] получаем [math] h(14,2) = (h_1(14) + 2\cdot h_2(14)) \bmod 13 = 9 [/math] . Ячейка с номером 9 свободна, значит записываем туда наш ключ.

    Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/math] дает различные последовательности ячеек для исследования.

    Простая реализация [ править ]

    Пусть у нас есть некоторый объект [math] item [/math] , в котором определено поле [math] key [/math] , от которого можно вычислить хеш-функции [math] h_1(key)[/math] и [math] h_2(key) [/math]

    Так же у нас есть таблица [math] table [/math] величиной [math] m [/math] , состоящая из объектов типа [math] item [/math] .

    Реализация с удалением [ править ]

    Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив [math]deleted[/math] типов [math]bool[/math] , равный по величине массиву [math]table[/math] . Теперь при удалении мы просто будем помечать наш объект как удалённый, а при добавлении как не удалённый и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.

    Альтернативная реализация метода цепочек [ править ]

    В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию сбалансированного дерева. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан линейный порядок. То есть при использовании данный типа [math]\mathbf[/math] или [math]\mathbf[/math] имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с [math]O(n)[/math] до [math]O(\log(n))[/math] . Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.

    Отчет по лабе 1

    Министерство образования и науки Российской Федерации

    Федеральное государственное бюджетное образовательное учреждение

    Высшего профессионального образования

    Уфимский государственный авиационный технический университет

    по лабораторной работе

    Выполнила: студентка гр. МО-204

    Постановка задачи

    Построить хеш — таблицу, содержащую последовательность из m = 54 элементов размерности n = 5. Элементы генерируются с помощью датчика случайных чисел.

    Хеш — функция — f(k) = ((k +13) / 31) % t, t – размер хеш-таблицы.

    Метод разрешения конфликта — квадратичные пробы.

    Переменные, используемые в программе

    int n=54; //Количество генерируемых элементов

    int n1=81; //Размер хэш-таблицы

    long int mas[100]; //Массив генерируемых элементов

    int hash[100]=<0>; //Хэш-таблица

    int adress; //Хэш-адрес

    int i0=1; //Номер пробы

    int k1=0; //Коэффициент заполнения таблицы = n/n1

    int k2=0; //Общее число проб

    Реализация

    Шаг 1. Генерируем элементы исходного массива, заданной размерности, с помощью функции генерации уникальных случайных чисел.

    Мастер Йода рекомендует:  Как написать блог на PHP
    Добавить комментарий