Как создать хеш таблицу python

Как создать хеш таблицу python

На этом шаге рассмотрим хеш-таблицы в Python .

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

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

book =

book — новая хеш-таблица. Добавим в book несколько цен:

book[

А теперь запросим цену авокадо:

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

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

Использование хэш-таблиц в 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 – бинарное красно-черное дерево. Во всем остальном эти два класса очень похожи.

Хеш-таблицы — Python: Cловари и множества

Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары «ключ-значение». В разных языках ему соответствуют разные типы данных. В Python — это Dictionary, в других языках:

• Ruby — Hash
• Lua — Table
• JavaScript — Object
• Elixir/Java — Map

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

В обычном индексированном массиве значения расположены по индексам, а значит его можно положить в память «как есть». С ассоциативными массивами все работает по-другому. У них нет индексов, которые бы могли определить порядок — значит, и нет простого способа добраться до значений.

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

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

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

data = <> data['key'] = 'value' 

Что такое хеширование

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

• Найти хеш, то есть хешировать ключ
• Привести ключ к индексу — например, через остаток от деления

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

Наиболее известны CRC32, MD5, SHA и много других типов хеширования:

# В Python есть библиотека zlib, содержащая алгоритм хеширования crc32 # Этот алгоритм удобен для наглядности import zlib # Любые данные, которые мы хотим хешировать, представляются в виде байтовой строки data = b'Hello, world!' hash = zlib.crc32(data) # Хеш всегда одинаковый для одних и тех же данных print(hash) # => 3957769958 

С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 — это хеш, полученный в результате хеширования данных коммита.

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

# Это делается для того, чтобы индексы не были слишком большими # Чем больше размер массива, тем больше памяти он занимает index = abs(hash) % 1000 # по модулю print(index) # => 958 

Как хеширование работает изнутри

Рассмотрим, как работает добавление нового значения в ассоциативный массив. Напомним, в Python он представлен типом данных Dictionary. Напишем такой код:

data = <> data['key'] = 'value' 

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

Мы создаем ассоциативный массив. Внутри интерпретатора происходит инициализация индексированного массива:

internal = [] 

data['key'] = 'value' 

hash = zlib.crc32(b'key') 

index = abs(hash) % 1000 

internal[index] = ['key', 'value'] 

Теперь посмотрим, как работает чтение данных:

data = <> data['key'] = 'value' print(data['key']) # => "value" 

Разберем, как этот код работает изнутри.

Интерпретатор хеширует ключ. Результатом хеширования становится число:

hash = zlib.crc32(b'key') 

index = abs(hash % 1000) 

return internal[index] # ['key', 'value'] 

Коллизии

Ключом в ассоциативном массиве может быть абсолютно любая строка, любой длины и содержания. Но здесь есть одно противоречие:

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

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

Такую ситуацию принято называть коллизией. Есть несколько способов разрешения коллизий . Каждому способу соответствует свой тип хеш-таблицы:

# Пример коллизии # Хеш-функция возвращает одинаковый хеш для разных строчных данных zlib.crc32(b'aaaaa0.462031558722291') # 1938556049 zlib.crc32(b'aaaaa0.0585754039730588') # 1938556049 

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

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

Хеш-таблицы

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

Пусть k — ключ, а h(x) — хеш-функция.

Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .

Коллизии

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

Есть несколько методов борьбы с коллизиями:

• метод цепочек;
• метод открытой адресации: линейное и квадратичное зондирование.

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

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

Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .

Псевдокод операций

chainedHashSearch(T, k) return T[h(k)] chainedHashInsert(T, x) T[h(x.key)] = x chainedHashDelete(T, x) T[h(x.key)] = NIL 

2. Открытая адресация

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

Существует несколько видов открытой адресации:

a) Линейное зондирование

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

h(k, i) = (h′(k) + i) mod m ,

• i =
• h'(k) — новая хеш-функция

Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть значение i увеличивается линейно.

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

b) Квадратичное зондирование

Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:

• c₁ и c₂ — положительные вспомогательные константы,
• i =

c) Двойное хэширование

Если коллизия возникает после применения хеш-функции h(k) , то для поиска следующей ячейки вычисляется другая хеш-функция.

h(k, i) = (h1(k) + ih2(k)) mod m

«Хорошие» хеш-функции

«Хорошие» хеш-функции не уберегут вас от коллизий, но, по крайней мере, сократят их количество.

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

1. Метод деления

Если k — ключ, а m — размер хеш-таблицы, то хеш-функция h() вычисляется следующим образом:

Например, если m = 10 и k = 112 , то h(k) = 112 mod 10 = 2 . То есть значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.

если m = 22, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 01 если m = 23, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 001 если m = 24, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 0001 если m = 2p, тогда h(k) = p биты порядком ниже, чем m

2. Метод умножения

• kA mod 1 отделяет дробную часть kA;
• ⌊ ⌋ округляет значение;
• A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.

3. Универсальное хеширование

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

Где применяются

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

Примеры реализации хеш-таблиц в Python, Java, Си и C++

Python

# Реализация хеш-таблицы в Python hashTable = [[],] * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable[index] = [key, data] def removeData(key): index = hashFunction(key) hashTable[index] = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 

Java

// Реализация хеш-таблицы в Java import java.util.*; class HashTable < public static void main(String args[]) < Hashtableht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); > > 

Cи

// Реализация хеш-таблицы в Cи #include #include struct set < int key; int data; >; struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) < return (key % capacity); >int checkPrime(int n) < int i; if (n == 1 || n == 0) < return 0; >for (i = 2; i < n / 2; i++) < if (n % i == 0) < return 0; >> return 1; > int getPrime(int n) < if (n % 2 == 0) < n++; >while (!checkPrime(n)) < n += 2; >return n; > void init_array() < capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) < array[i].key = 0; array[i].data = 0; >> void insert(int key, int data) < int index = hashFunction(key); if (array[index].data == 0) < array[index].key = key; array[index].data = data; size++; printf("\n Ключ (%d) вставлен \n", key); >else if (array[index].key == key) < array[index].data = data; >else < printf("\n Возникла коллизия \n"); >> void remove_element(int key) < int index = hashFunction(key); if (array[index].data == 0) < printf("\n Данного ключа не существует \n"); >else < array[index].key = 0; array[index].data = 0; size--; printf("\n Ключ (%d) удален \n", key); >> void display() < int i; for (i = 0; i < capacity; i++) < if (array[i].data == 0) < printf("\n array[%d]: / ", i); >else < printf("\n Ключ: %d array[%d]: %d \t", array[i].key, i, array[i].data); >> > int size_of_hashtable() < return size; >int main() < int choice, key, data, n; int c = 0; init_array(); do < printf("1.Вставить элемент в хэш-таблицу" "\n2.Удалить элемент из хэш-таблицы" "\n3.Узнать размер хэш-таблицы" "\n4.Вывести хэш-таблицу" "\n\n Пожалуйста, выберите нужный вариант: "); scanf("%d", &choice); switch (choice) < case 1: printf("Введите ключ -:\t"); scanf("%d", &key); printf("Введите данные-:\t"); scanf("%d", &data); insert(key, data); break; case 2: printf("Введите ключ, который хотите удалить-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Размер хеш-таблицы-:%d\n", n); break; case 4: display(); break; default: printf("Неверно введены данные\n"); >printf("\nПродолжить? (Нажмите 1, если да): "); scanf("%d", &c); > while (c == 1); > 

C++

// Реализация хеш-таблицы в C++ #include #include using namespace std; class HashTable < int capacity; list*table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) < int i; if (n == 1 || n == 0) < return 0; >for (i = 2; i < n / 2; i++) < if (n % i == 0) < return 0; >> return 1; > int getPrime(int n) < if (n % 2 == 0) < n++; >while (!checkPrime(n)) < n += 2; >return n; > int hashFunction(int key) < return (key % capacity); >void displayHash(); >; HashTable::HashTable(int c) < int size = getPrime(c); this->capacity = size; table = new list[capacity]; > void HashTable::insertItem(int key, int data) < int index = hashFunction(key); table[index].push_back(data); >void HashTable::deleteItem(int key) < int index = hashFunction(key); list::iterator i; for (i = table[index].begin(); i != table[index].end(); i++) < if (*i == key) break; >if (i != table[index].end()) table[index].erase(i); > void HashTable::displayHash() < for (int i = 0; i < capacity; i++) < cout " > int main() < int key[] = ; int data[] = ; int size = sizeof(key) / sizeof(key[0]); HashTable h(size); for (int i = 0; i

СodeСhick.io - простой и эффективный способ изучения программирования.