Хэш таблица c реализация

Хэш таблица c реализация

Один из наиболее эффективных способов реализации словаря — хеш-таблица. Среднее время поиска элемента в ней есть 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, имеется значительная свободы в выборе длины таблицы.

    размер время размер время
    1 869 128 9
    2 432 256 6
    4 214 512 4
    8 106 1024 4
    16 54 2048 3
    32 28 4096 3
    64 15 8192 3

    Таблица 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% всей таблицы.

    Хеш-таблица (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 приложений

    Программирование, Алгоритмы, С++, C#, Java, Python и другие вещи

    четверг, 17 января 2013 г.

    Хеш-таблица (Hash-Table). Реализация C++.

    Чтобы понять, что такое хеш-таблица, вспомним массив. Мы можем получить доступ к элементу с помощью его ключа, причем может быть такой случай, что есть ячейки содержащие элементы и есть не содержащие.
    Представим ситуацию, что нам нужно найти элемент, например, массив состоит из строк большой длины. Нам придется нашу подстроку поиска сравнивать со всеми элементами массива, что неудобно, так как поиск займет O(n). НО мы хотим O(1). Решение есть! Использовать специальную хеш функцию, для того, чтобы мы имели доступ по индексу.

    • Каждой строке соответствует индекс равный (n=длина строки-1). Например: строка "Alex" индекс 3. Вот так можно записать строки.
    • Хеш функция у нас будет: Hash_Func(string)=Strlen(string) (то есть вычисление длины).
    • Доступ к массиву мы получаем вот так: Mas[Hash_Func(string)].
    Читайте также:  Какой программой пользуется мармок для создания музыки

    length value
    ————————
    2 "joe"
    3 "Alex"
    4 "Pavel"
    Но! вот в чем беда! Если мы хотим вставить еще 1 имя, например "Petr", то этому имени будет соответствовать ОДИН И ТОТ ЖЕ КЛЮЧ 3, который является индексом 3. Это называется Коллизией, когда один и тот же ключ указывает на несколько значений ключа.
    Иллюстрация коллизии (2 ключа относятся к одной и той же ячейки массива, ключи k2 и k3):

    Разрешение случаев с коллизией является важной задачей Computer Science. Решениями проблемы являются:

    1. Метод цепочек (открытое хеширование).
    2. Метод открытой адресации (закрытое хеширование).
    1. Идея метода цепочек состоит в том, что все элементы множества, которые относятся к одному и тому же ключу входят в связный список.

    Возвращаясь к нашему примеру с именами, переделаем его в соответствии с новым методом:
    length value
    ————————
    2 *head1 ["Joe"->"Rex"->Null]
    3 *head2 ["Alex"->"Petr"->"Oleg"->Null]
    4 *head3 ["Pavel"->Null]
    В этом примере 0,1,5 элементы указатели равны Null
    Процедура вставки происходит так: Вычисляется хеш-функция от строки и вставляется в голову списка (push_front) на определенный индекс равный значению функции.
    Вставка происходит за O(1).
    Поиск или удаление элемента зависит от длины списка, худший случай: O(n) — когда, все элементы хешируются в одну и ту же ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка k=n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. В этом случае время поиска: O(1+k), это показано в книжке Кормана, могу скинуть ссылку на нее, если интересно.
    Добавлю, что в случае, когда коэффициент заполнения будет слишком велик, надо будет увеличить размер массива и, возможно, перестроить таблицу.

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

    Общий прием состоит в следующем: если хеш-функция вырабатывает позицию для первого кандидата i = Hash_Func(key) Mod (capacity) , то последующие позиции определяются как i + increment , i +2 * increment , i +3 * increment и так далее, все по модулю capacity . Величина increment вычисляется как:
    Hash_Func(key) Mod (capacity -1)

    i,i1,i2 ячейки заняты, i=2, i1=4, i2=6, i3=8, capacity=11
    Последующие index=i+increment (increment = 2 Mod 10 = 2 )

    Хеш-таблицы имеют очень большое практическое применение:

    • Для поиска информации о водители лишь по его номеру в водительском удостоверении.

    • Таблица символов компилятора. Хеширование является методом ускорения поиска. Компилятор встре­чает некоторую лексему и пытается найти ее в своей базе данных или таб­лице символических имен. Таблица символических имен современного компилятора в MS Windows может содержать несколько тысяч или десятков тысяч лексем. Для ускорения поиска был придуман следующий прием. Компилятор, найдя лексему в тексте программы, определяет ее хеш-ключ. Наша лексема — это просто слово, состоящее из последовательности кодов символов. Для определения хеш-кода следует сложить все коды символов. Лексем с таким хеш-кодом в базе данных уже значительно меньше. Компи­лятор определяет номер списка с заданным кодом и перебирает этот спи­сок, а не всю базу данных.
    • При программировании шахмат тоже используется хеширование. Основная особенность состоит в том, что хеш-индекс должен очень точно отражать позицию, и поиск должен производиться максимально быстро. У нас даже нет времени на перебор списков с одним индексом. Списков, как правило, нет вообще. Для каждого значения хеш-ключа существует только одна по­зиция. Если возникла коллизия и встретилась позиция с таким же ключом, то она записывается поверх прежней. Зачем при программировании шахмат и других подобных игр хеширование и запоминание позиций? Дело в том, что при переборе мы имеем не дерево игры в прямом смысле, а граф. По­зиции повторяются через некоторое количество полуходов, и даже в одну и ту же позицию можно прийти различными путями. Можно воспользоваться некоторой информацией о позиции, которая уже встречалась. Самое про­стое и эффективное — это использовать позицию, чтобы улучшить порядок ходов. Это особенно выразительно при итеративных углублениях. Улучше­ние упорядочивания ходов — основное назначение хеш-таблицы. Переста­новки или повторы позиций тоже играют свою роль. Особенно их много в конце игры.
    • Для баз данных телефонных номеров.
    • Каталог книг.
    • Для хранения паролей пользователей.
    • Браузер хранит адреса посещенных страниц в хеш-таблице.

    Реализация на языке С++ доделывается, не хватает нескольких функций. Если, есть какие-то предложения, пишите в комментарии.

    Ссылка на основную публикацию
    Функции в вольфрам математика
    Функции пользователя Хотя в систему входят многие сотни встроенных функций (начиная от элементарных и кончая специальными математическими функциями и системными...
    Учимся рисовать в paint
    Серия видео уроков «Создание компьютерного рисунка в программе Paint» МОУ «Межборская средняя общеобразовательная школа» (Уроки предназначены для детей 9-12 лет,...
    Учиться без троек сканворд
    Музыкант, играющий на барабанах, тарелках Передовой работник производства (ударник) Часть затвора стрелкового оружия (ударник) "Барабанщик" коммунистического труда (устар.) (ударник) "Барабанщик"...
    Функция abs в паскале
    Возвращает абсолютную величину параметра. Объявление Function Abs(X) : (тип параметра); Режим Windows, Real, Protected Замечания Параметр X — выражение вещественного...
    Adblock detector