Что такое хэш таблица python

Python – хэш-таблица

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

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

В Python типы данных Dictionary представляют реализацию хеш-таблиц. Ключи в словаре удовлетворяют следующим требованиям.

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

Таким образом, мы видим реализацию хеш-таблицы с использованием словарных типов данных, как показано ниже.

Доступ к значениям в словаре

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

# Declare a dictionary dict = 'Name': 'Zara', 'Age': 7, 'Class': 'First'> # Accessing the dictionary with its key print "dict['Name']: ", dict['Name'] print "dict['Age']: ", dict['Age']

Когда приведенный выше код выполняется, он дает следующий результат –

dict['Name']: Zara dict['Age']: 7

Обновление словаря

Вы можете обновить словарь, добавив новую запись или пару ключ-значение, изменив существующую запись или удалив существующую запись, как показано ниже в простом примере –

# Declare a dictionary dict = 'Name': 'Zara', 'Age': 7, 'Class': 'First'> dict['Age'] = 8; # update existing entry dict['School'] = "DPS School"; # Add new entry print "dict['Age']: ", dict['Age'] print "dict['School']: ", dict['School']

Когда приведенный выше код выполняется, он дает следующий результат –

When the above code is executed, it produces the following result − dict['Age']: 8 dict['School']: DPS School

Удалить элементы словаря

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

dict = 'Name': 'Zara', 'Age': 7, 'Class': 'First'> del dict['Name']; # remove entry with key 'Name' dict.clear(); # remove all entries in dict del dict ; # delete entire dictionary print "dict['Age']: ", dict['Age'] print "dict['School']: ", dict['School']

Это дает следующий результат. Обратите внимание, что возникает исключение, потому что после словаря del dict больше не существует –

Хеш-таблица

Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [math]H[/math] , элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код [math]i = h(key)[/math] играет роль индекса в массиве [math]H[/math] , а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).

Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.

Вероятность коллизий при вставке в хеш-таблицу превышает 50%

Пусть хеш-таблица имеет размер [math]len[/math] и в нее добавляют [math]n[/math] элементов. Рассмотрим [math]

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

‘(n) = \left( 1 — \dfrac\right )\cdot \left( 1 — \dfrac\right )\dots\left( 1 — \dfrac\right ) = \dfrac> = \dfrac \cdot \left (len — n \right)!>[/math]

Тогда [math]

(n)[/math] — вероятность возникновения коллизии равна: [math]p(n) = 1 —

‘(n)[/math] ,

Способ разрешения коллизий — важная составляющая любой хеш-таблицы.

Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с прямой адресацией; в них все операции, такие как: поиск, вставка и удаление работают за [math]O(1)[/math] .

Если мы поделим число хранимых элементов на размер массива [math]H[/math] (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. load factor). От этого параметра зависит среднее время выполнения операций.

Хеширование

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

Определение:

[math]U [/math] — множество объектов (универсум).
[math]h : U \rightarrow S = \mathcal 0 \dots m — 1 \mathcal [/math] — называется хеш-функцией, где множество [math]S[/math] хранит ключи из множества [math]U[/math] .
Если [math]x \in U[/math] значит [math]h(x) \in S[/math]
Коллизия (англ. collision): [math]\exists x \neq y : h(x) = h(y)[/math]

Виды хеширования

По способу хранения:

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

Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.

По виду хеш-функции:

Свойства хеш-таблицы

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

Хеширование в современных языках программирования

Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.

Java

HashMap [1] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
HashSet [2] — реализация интерфейса множества с использованием хеш-таблицы,
LinkedHashMap [3] — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.

unordered_map [4] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
unordered_set [5] — реализация интерфейса множества с использованием хеш-таблицы.

dict [6] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
set [7] — реализация интерфейса множества с использованием хеш-таблицы.

Примечания

↑HashMap — Java Platform SE 7
↑HashSet — Java Platform SE 7
↑LinkedHashMap — Java Platform SE 7
↑unordered_map — cplusplus.com
↑unordered_set — cplusplus.com
↑dictobject.c — https://github.com/python/cpython
↑setobject.c — https://hg.python.org

Источники информации

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г. — 824 стр. — ISBN 0-201-89685-0
Википедия — Хеш-таблица

Дискретная математика и алгоритмы
Хеширование
Структуры данных

Использование хэш-таблиц в Python и С++

то формируется хэш-таблица с ключами ‘one’, ‘two’, ‘five’ и соответствующими значениями 1, 2, 5. Если нам нужно добавить в эту хэш-таблицу еще какой-либо ключ, то это можно сделать так:

d['three'] = 3

А считывание значений по ключу выполняется, например, командой:

value = d['one'] print(value)

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

d[[1,2,3]] = 10

то в процессе выполнения этой команды будет сгенерирована ошибка: TypeError: unhashable type: ‘list’ Что означает, что список (list) относится к нехэшируемым данным и не может использоваться в качестве ключа хэш-таблицы. По аналогии со словарями в Python работает и множество:

s = {'one', 'two', 'five'}

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

s = {'one', (1, 2, 3), True, 10, 5.8}

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

s = {'one', (1, 2, 3), True, 10, 5.8, [1, 2, 3]}

Здесь последний элемент список (list) относится к изменяемому, а значит, нехэшируемому типу.

Хэш-таблицы в С++

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

#include

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

int main() { setlocale(LC_ALL, "ru"); using namespace std; unordered_mapstring, int> ar; return 0; }

Класс unordered_map в целом имеет тот же функционал (тот же набор методов), что и класс map, о котором мы уже с вами говорили. Только map реализован на основе красно-черного бинарного дерева, а unordered_map – на основе хэш-таблиц. Поэтому в программе выбирается тот класс, который предпочтительнее использовать для хранения и обработки данных. Так как функционал этих классов схожий, то я кратко продемонстрирую работу с unordered_map. При создании объекта, мы в угловых скобках указываем тип ключа и тип значения. В примере ключ имеет тип string (строка), а значение тип int (целое число). Сам объект ar представляет собой пустую хэш-таблицу. Чтобы внести в нее какие-либо данные, можно воспользоваться или методом insert():

ar.insert(pairstring, int>("one", 1)); ar.insert(make_pair("three", 3));

но проще и лучше методом emplace():

ar.emplace("four", 4);

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

for (auto& item : ar) { cout  item.first  " "  item.second  endl; }

В результате увидим на экране строчки: one 1
three 3
four 4 Также добавлять новые данные можно с помощью оператора квадратные скобки:

ar["five"] = 5;

И читать значения по ключу:

auto val = ar["one"]; cout  val  endl;

Для удаления ключа из хэш-таблицы можно воспользоваться методом erase():

auto it = ar.erase("three");

Данный метод возвращает булево значение false, если удаление ключа по каким-либо причинам не было выполнено и true в противном случае. Для поиска элемента по ключу используется метод find():

auto it = ar.find("two");

Данный метод возвращает итератор на пару ключ-значение, если указанный ключ был найден, либо значение ar.end(), если ключ не найден.

Класс unordered_set

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

#include

А, затем, в функции main() создать экземпляр этого класса, например, так:

int main() { setlocale(LC_ALL, "ru"); using namespace std; unordered_setint> s = { 1, 2, 3 }; for (auto& item : s) { cout   <" "  ; } return 0; }

Мы здесь сразу инициализируем множество значениями 1, 2, 3. В результате создается хэш-таблица с такими ключами и далее, с помощью цикла for, мы перебираем эту хэш-таблицу и выводим значения ключей в консоль. Я не буду подробно останавливаться на работе с классом unordered_set, так как он содержит подобный набор методов, что и класс set. Основные из них приведены в таблице ниже.

Метод	Описание	Сложность
begin(), cbegin()	Возвращает итератор на первый элемент списка	O(1)
end(), cend()	Возвращает итератор на последний элемент списка	O(1)
size()	Возвращает число элементов в списке	O(1)
insert()	Вставка нового элемента в произвольную позицию	O(1)
erase()	Удаление произвольного элемента списка	O(1)
find()	Поиск элемента по значению	O(1)
clear()	Очистка двусвязного списка	—
empty()	Возвращает true, если множество пустое и false в противном случае	O(1)

Например, мы можем выполнить следующие операции:

cout  s.size()  endl; s.insert(4); s.erase(2); auto it = s.findint>(1); if (it != s.end()) { cout  *it  endl; }

Главное здесь знать, что unordered_set использует хэш-таблицу для хранения и обработки значений, а класс set – бинарное красно-черное дерево. Во всем остальном эти два класса очень похожи.

Хэш-таблицы. Что это такое и как работают

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

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

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

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

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

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

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

Добавление элементов в хэш-таблицу

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

Ключ	Значение
a	а
b	б
c	с
d	д
f	ф
…	…

Причем нам наперед неизвестно, сколько именно букв будет храниться в хэш-таблице. Поэтому, чтобы зря не расходовать память, начальный размер таблицы будет иметь m=5 элементов. Сами ячейки таблицы будут хранить адреса на объекты с данными. Если данных нет, то указатели принимают значение NULL. Далее, у нас имеется хэш-функция, которая для каждой буквы латинского алфавита вычисляет индекс в массиве T. Предположим, мы хотим по ключу b записать значение б. На вход хэш-функции подается символ b. На выходе получаем индекс массива, по которому этот ключ должен располагаться в таблице. Пусть это будет индекс 1: Затем, в памяти создается новый объект с ключом b и значенем б, и адрес этого объекта сохраняется во втором элементе таблицы. То есть, массив хранит не сами данные, а ссылки на объекты с данными. Это наиболее частая реализация хэш-таблиц. В результате мы добавили новый ключ b и его значение б в хэш-таблицу. На уровне языков программирования эта операция часто записывается в виде:

T["b"] = "б"

Разумеется, если T – это хэш-таблица. По аналогии можно добавить еще несколько ключей и значений. Например, ключи f, d, u: И наш массив почти заполнен! В теории хэш-таблиц степень их заполненности определяется коэффициентом: α = n / m где n – количество хранимых ключей (в нашем примере 4); m – размер массива (в нашем примере 5). Получаем, значение степени заполнения таблицы: α = 4 / 5 = 0,8 То есть, пока этот коэффициент меньше единицы, в массиве есть свободные элементы, куда теоретически еще можно добавить новые ключи. Если α = 1, то массив заполнен полностью. Если же α > 1, то число ключей превышает размер хэш-таблицы. (Как такое может быть, мы еще будем говорить.) Итак, на данный момент коэффициент α = 0,8, значит, массив почти заполнен. Что делать дальше? Выход только один: увеличить размер таблицы, то есть, рассматривать массив как динамический и, например, при α близкой к 1 увеличивать его размер в 2 раза. Давайте так и сделаем. Сначала мы должны в памяти создать новый массив длиной в 2 раза больше предыдущего. После этого хэш-функция будет уже выдавать новый диапазон индексов [0; 9]. Поэтому элементы должны не просто копироваться в новый массив, а заново прогоняться через новую хэш-функцию. Получим (как пример): Только после этого мы сюда можем добавлять новые ключи. Вот общий принцип работы алгоритма добавления ключей и значений в хэш-таблицы. В среднем, эта операция выполняется за фиксированное время O(1).

Разрешение коллизий в хэш-таблицах

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

метод цепочек;
метод открытой адресации.

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

T["b"] = б T["ba"] = ба T["d"] = д T["f"] = ф T["bb"] = бб T["fa"] = фа

И хэш-функция для ключей с одинаковыми первыми буквами выдает одни и те же индексы таблицы. Тогда, чтобы сохранить несколько разных ключей по одному и тому же индексу, формируется двусвязный список, на начало которого ведет указатель ptr. В элементах этого двусвязного списка сохраняются пары ключ-значение. Это и есть принцип разрешения коллизий по методу цепочек. У такого решения есть положительные и отрицательные стороны. К положительным можно отнести простоту реализации. Сформировать двусвязные списки там, где необходимо хранить несколько ключей, не составляет особого труда. Также относительно быстро происходит вставка новых ключей и удаление существующих в таких списках (цепочках). А основным недостатком является возможность появления длинных цепочек в хэш-таблицах. Тогда поиск нужного ключа может занять продолжительное время и преимущества хэш-таблиц будут сведены к нулю. Очевидно, чтобы избежать такого неблагоприятного случая (образования длинных цепочек), нужно правильно выбирать хэш-функцию, которая бы равномерно распределяла возможные ключи по индексам таблицы. Благо, существуют подходы, позволяющие создавать такие функции, но об этом мы еще будем говорить. А сейчас посмотрим, как в хэш-таблицах со списками выполняется поиск и удаление ключей.

Алгоритм поиска ключей

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

val = T["ba"]

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

p = ptr

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

Алгоритм удаления ключей

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

del T["ba"]

Вначале также подаем этот ключ на вход хэш-функции и получаем индекс 1 в таблице. По этому индексу хранится несколько ключей в двусвязном списке. С помощью временного указателя p находим элемент с ключом «ba». Это второй элемент. И удаляем его. (Как удалять элементы в двухсвязных списках мы с вами уже говорили на предыдущих занятиях). Все, ключ удален из хэш-таблицы. Если происходит удаление единственного ключа в ячейке, например, ключа «d», то проверяется, что в единственном элементе действительно хранится ключ «d», если так, то объект удаляется и ячейка принимает значение NULL. Наконец, если пытаемся удалить не существующий в таблице ключ, например, «s», то либо сразу попадаем в ячейку со значением NULL, либо на цепочку из ключей, в которой ключ «s» будет отсутствовать. В любом случае, при отсутствии ключа никаких действий с таблицей не выполняется и она остается в неизменном виде.