Хеш-таблицы — 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 студентов
Наши выпускники работают в компаниях:
Хеш-таблицы — JS: Объекты
Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары ключ-значение. У него есть и другие названия: «словарь», «мап» (от слова map). В разных языках ему соответствуют разные типы данных. В JavaScript — это Object, в других языках:
- Ruby — Hash
- Lua — Table
- Python — Dictionary
- Elixir/Java — Map
Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров. Фактически все предыдущие уроки по объектам в JavaScript были посвящены тому, как использовать объекты в качестве ассоциативных массивов.
Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память «как есть». У него нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные в памяти, она включает в себя логику.
Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри. Эта информация крайне важна для разработчиков, которые хотят по-настоящему разбираться в том, что они делают. Она снимает «магичность» с происходящего внутри языка и дает понимание цены, которую приходится платить за удобство использования объектов.
Итак, что примерно происходит, когда мы выполняем код:
const data = <>; data['key'] = 'value'; Хеширование
Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).
Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется «хеш-функцией», а результат называют «хешем» или «хеш-суммой». Наиболее известны CRC32, MD5 и SHA (много разновидностей).
// В JavaScript нет встроенной поддержки алгоритма хеширования crc32 (удобен для наглядности) // Поэтому используется сторонняя библиотека import crc32 from 'crc-32'; const data = 'Hello, world!'; // Любые данные, которые мы хотим хешировать const hash = crc32.str(data); // Хеш всегда одинаковый для одних и тех же данных! console.log(hash); // => -337197338 С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 не что иное, как хеш, полученный в результате хеширования данных коммита.
После того, как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:
// Это делается для того, чтобы индексы не были слишком большими // Чем больше размер массива, тем больше памяти он занимает const index = Math.abs(hash) % 1000; // по модулю console.log(index); // => 338 За кулисами
Рассмотрим процесс добавления нового значения в ассоциативный массив (напоминаем, что в JavaScript он представлен типом данных Object). Программист пишет:
const data = <>; data['key'] = 'value'; Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:
// Для простоты показано на JavaScript, хотя в реальности всё это происходит на более низком уровне // 1. Создание ассоциативного массива приводит к инициализации индексированного массива внутри интерпретатора. const internal = []; // Во время присвоения значения `data['key'] = 'value'`, интерпретатор выполняет несколько действий: // 2. Хеширует ключ. Результатом хеширования становится число. const hash = crc32.str('key'); // 3. Число, полученное на предыдущем шаге, преобразуется в индекс массива. const index = Math.abs(hash) % 1000; // В значение внутреннего индексированного массива, по найденному индексу, записывается еще один массив, // первым элементом которого становится ключ `'key'`, а вторым значение `'value'`. internal[index] = ['key', 'value']; Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже, там где мы поговорим про коллизии.
Теперь посмотрим на чтение:
const data = <>; data['key'] = 'value'; console.log(data['key']); // => "value" // Для простоты показано на JavaScript, хотя в реальности всё это происходит на более низком уровне // 1. Хешируется ключ. Результатом хеширования становится число. const hash = crc32.str('key'); // 2. Число, полученное на предыдущем шаге преобразуется в индекс массива. const index = Math.abs(hash % 1000); // 3. Если индекс существует, то извлекается массив, который находился внутри, и возвращается наружу. return internal[index]; // ['key', 'value'] Коллизии
Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей — бесконечно. В свою очередь, результат работы хеш-функции — строка фиксированной длины, а значит множество всех выходных значений — конечно.
Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (где под одним хешем лежит несколько разных значений — как если бы под одним индексом в массиве лежало два разных элемента). Такую ситуацию принято называть коллизией. Есть несколько способов разрешения коллизий (открытая адресация, метод цепочек), и каждому из них соответствует свой тип хеш-таблицы.
// Пример коллизии // Хеш-функция возвращает одинаковый хеш для разных строчных данных! crc32.str('aaaaa0.462031558722291'); // 1938556049 crc32.str('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) Квадратичное зондирование
Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:
- c1 и c2 — положительные вспомогательные константы,
- 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 биты порядком ниже, чем m2. Метод умножения
- 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 - простой и эффективный способ изучения программирования.
Хеш-таблица
Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [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
- Википедия — Хеш-таблица
- Дискретная математика и алгоритмы
- Хеширование
- Структуры данных