Хэш карты что это

Хэш карты что это

Ассоциативный массив. Введение

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

1. Пусть нам необходим массив, который состоит из большого числа элементов. Массив имеет размер порядка 2 128 элементов, но хранятся в нём всего около 2 10 – 2 20 штук. Проблема в том, что нужные элементы в массиве располагаются не обособленно, а размазаны по всему массиву, так что выделить подмассив достаточно малого размера и работать с ним не получится. Создать массив размера 2 128 мы тоже не можем.

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

Решение задачи

Пусть нужно хранить 3 значения, с индексами 1001883726, 4524352321524 и 77656433109. Для этого создадим массив A размером в N раз больше, чем элементов. Как находить это число N не известно пока. Возьмём массив размером 10 элементов.

После этого, вместо индекса будем брать остаток от деления на размер массива (в нашем случае 10). Тогда, первый элемент будет иметь индекс 6, и мы поместим его в массив A[6]. Второй элемент в массив под номером 4, третий под номером 9.

Очевидно, что могут появиться элементы с одинаковым индексом. Пусть теперь мы добавляем элемент с индексом 3776. Элемент A[6] же занят, поэтому мы создаём на месте элемента 6 односвязный список и привязываем новое значение к старому.

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

Вы успели заметить, что в таком описании очень много условностей. Начнём разбираться с неизвестными X, M и N.

Начальный размер массива, в принципе, может быть любым, хоть единицей. Нам больше важен коэффициент заполнения X, при котором будет происходить пересборка. Это значение называют load factor. В языке C# это значение равно 0.72, а в Java 0.75. Эти значения получены после анализ большого количества кода и считаются для данных языков оптимальными. Анализ мы проводить не будем, а просто возьмём на веру значение 0.72.

Значение 0.72 значит, что после заполнения исходного массива более чем на 72 процента его нужно будет увеличить в M раз. M обычно берут равным 2. То есть, если в нашем массиве изначально 100 элементов , то после добавления 72 пар , массив будет увеличен в 2 раза, то есть, станет равным 200.

Пересборку будем осуществлять следующим образом: создадим новую карту нового размера, поместим в неё элементы из старого массива, удалим старую карту.

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

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

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

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

Описанная нами структура называется ассоциативным массивом с закрытой адресацией. Также существует ассоциативный массив с открытой адресацией. В нём вместо создания односвязного списка, по определённому алгоритму мы ищем пустую ячейку в текущем массиве. Рассмотрим его позднее.

Вторая задача

Мы хотим реализовать структуру, подобную массиву, но в качестве индекса хотим использовать строку. То есть, обращаться к массиву как a[“Pupkin”], а не a[1772634]. Очевидно, что если бы мы могли каждой строке поставить в соответствие число, то тогда можно было бы свести вторую задачу к первой.

Третья задача

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

Для решения второй и третьей задачи воспользуемся хэшированием.

Как говорит Википедия, Хеширование (иногда "хэшировани", англ. hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest).

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

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

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

Из этого следует, что ключ должен поддерживать операцию равенства. К счастью, почти все объекты поддерживают эту операцию (исключение, например, это значение NaN, для которого не поддерживается свойство рефлексии a == a).

Хэш-карта. Реализация.

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

Хэш-карта — это реализация интерфейса ассоциативного массива. Ассоциативный массив должен поддерживать операции

  • PUT(ключ, значение) для вставки новой пары
  • GET(ключ) для получения значения по ключу
  • REMOVE(ключ) для удаления пары по ключу

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

Структура Entry – пара

Далее, структура для реализации односвязного списка

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

Теперь, собственно, сама структура "хэш-карта".

Для упрощение работы введено ещё одно значение limit. Это целочисленное значение количества элементов, при превышении которого произойдёт пересборка.

Функция создания карты

Здесь мы защищаем пользователя от ввода "плохих" по нашему мнению значений. То есть, минимальное значение элементов массива не может быть меньше INITIAL_SIZE и т.д.

Читайте также:  Не найдена среда восстановления

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

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

Вспомогательная функция rehashUp. Создаём новую карту с новыми размерами, проходим все значения и вставляем их в новую карту.

Поиск элемента. Возвращаем только значение пары

Удаление элемента. Заметьте, здесь мы возвращаем указатель на всю пару, так что при использовании необходимо будет явно удалять это значение.

Функция, которая проходит по всей карте и применяет функцию f ко всем парам.

Например, вот так

Удаление всей карты будем проводить совместно с удалением всех пар. Именно для этого мы создавали freeEntry

Основные преимущества хэш-карты это постоянство скорости вставки, удаления и поиска в среднем случае. Кроме того, ключ в карте не требует реализации операции "больше-меньше", требуется наличие операции равенства и хэш-функции. Из-за этого возникают и свои проблемы. Так как значения хранятся неупорядоченно, то поиск максимума и минимума будут порядка 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 приложений

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

P.S. Так кстати все-таки какой алгоритм лучше? С открытой или закрытой адресацией?

  • Вопрос задан более трёх лет назад
  • 668 просмотров

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

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

Ссылка на основную публикацию
Хорошие характеристики для ноутбука
На сегодняшний день портативной электроникой никого не удивишь - персональным носимым компьютером имеют право именоваться не только планшеты, плееры и...
Фото для срисовки легкие но красивые карандашом
Хотите научиться рисовать, но не знаете с чего начать? Подборка самых простых и легких картинок для срисовки помогут создать красивый...
Фото для школьной беседы
Если обычный диалог подразумевает участие только двух пользователей, то в беседу можно позвать нескольких друзей. Эта функция удобна, если нужно...
Хорошие щетки стеклоочистителя отзывы
Проверяем щетки стеклоочистителей. На испытаниях — 8 брендов. Сегодня можно определить к себе на службу дворника любой националь… простите, конструкции:...
Adblock detector