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

Ассоциативные массивы

Хэш-таблицы обычно используются для реализации многих типов таблиц в памяти. Они используются для реализации ассоциативных массивов (массивов, индексами которых являются произвольные строки или другие сложные объекты), особенно в интерпретируемых языках программирования, таких как Ruby, Python и PHP.

При сохранении нового элемента в мультикарте и столкновении хэшей мультикарта безоговорочно сохраняет оба элемента.

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

Индексирование базы данных

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

Кэши

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

Наборы (сеты)

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

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

Представление объекта

Некоторые динамические языки, такие как Perl, Python, JavaScript, Lua и Ruby, используют хэш-таблицы для реализации объектов. В этом представлении ключи - это имена членов и методов объекта, а значения - указатели на соответствующий член или метод.

Уникальное представление данных

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

Реализации в языках программирования

Многие языки программирования предоставляют функциональность хэш-таблиц либо в виде встроенных ассоциативных массивов, либо в качестве стандартных библиотечных модулей. Например, в C++ 11 класс unordered_map предоставляет хэш-таблицы для ключей и значений произвольного типа.

Язык программирования Java (включая вариант, используемый в Android) включает в себя общие коллекции HashSet, HashMap, LinkedHashSet и LinkedHashMap.

В PHP 5 и 7 движок Zend 2 и движок Zend 3 (соответственно) используют одну из хэш-функций от Daniel J. Bernstein для генерации хэш-значений, используемых при управлении отображениями указателей данных, хранящихся в хэш-таблице. В исходном коде PHP он помечен как DJBX33A.

Реализация встроенной в Python хэш-таблицы в форме типа dict, а также hash типа (%) в Perl используется внутри для реализации пространств имен и, следовательно, должна уделять больше внимания безопасности, то есть атакам на коллизии. set в Python также использует внутренние хэши для быстрого поиска (хотя они хранят только ключи, а не значения).

В .NET Framework поддержка хэш-таблиц обеспечивается через неуниверсальные классы Hashtable и generic Dictionary, которые хранят пары ключ-значение, и универсальный класс HashSet, в котором хранятся только значения.

В Ruby хэш-таблица использует модель открытой адресации начиная с Ruby 2.4 и далее.

В стандартной библиотеке Rust обобщенные структуры HashMap и HashSet используют линейное пробирование с Robin Hood bucket stealing.

ANSI Smalltalk определяет классы Set/IdentitySet и Dictionary/IdentityDictionary. Все реализации Smalltalk предоставляют дополнительные (еще не стандартизированные) версии WeakSet, WeakKeyDictionary и WeakValueDictionary.

Переменные массива Tcl - это хэш-таблицы, а словари Tcl - это неизменяемые значения, основанные на хэшах. Функциональность также доступна в виде функций библиотеки C Tcl_InitHashTable et al. (для общих хэш-таблиц) и Tcl_NewDictObj et al. (для значений словаря). Производительность была независимо оценена как чрезвычайно конкурентоспособная.

История

Идея хэширования возникла независимо в разных местах. В январе 1953 года Ганс Питер Лун написал внутренний меморандум IBM, в котором использовалось хэширование с цепочкой. Джин Амдаль, Элейн М. Макгроу, Натаниэль Рочестер и Артур Самуэль реализовали программу с использованием хэширования примерно в одно и то же время. Открытая адресация с линейным пробированием (относительно простой степпинг) приписывается Амдалю, но Ершов (в России) придерживался той же идеи.

Поиск по этому блогу

Alex tools