Что такое хэш таблица
Перейти к содержимому

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

  • автор:

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

    Примечания

    1. ↑HashMap — Java Platform SE 7
    2. ↑HashSet — Java Platform SE 7
    3. ↑LinkedHashMap — Java Platform SE 7
    4. ↑unordered_map — cplusplus.com
    5. ↑unordered_set — cplusplus.com
    6. ↑dictobject.c — https://github.com/python/cpython
    7. ↑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
    • Википедия — Хеш-таблица
    • Дискретная математика и алгоритмы
    • Хеширование
    • Структуры данных

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *