Главная » Java, Структуры данных и алгоритмы » Хеш-таблицы примеры применения

0

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

хеш-таблица (hash table). Хотя в крайних случаях, как следует из нижеизложенного, время выполнения операций АТД «словарь» при использовании хеш-таблиц может составить 0(п) времени, где п — количество объектов в словаре. Предполагается, что хеш-таблица может выполнять эти операции за время 0(1). Она состоит из двух основных компонентов, первым из которых является массив сегментов (bucket array).

Массивы сегментов

Массив сегментов хеш-таблицы представляет собой массив А размером N, где каждая ячейка рассматривается как «ведро» (bucket), то есть контейнер для пар «ключ-элемент», а целое число N определяет вместимость (объем) массива. Если ключами являются целые числа, расположенные в пределах [О, N- 1], то массив сегментов — это все, что требуется. Элемент е с ключом к просто вводится в сегмент А[к]. Любые сегментные ячейки, ассоциируемые с ключами, не представленными в словаре, должны содержать объект NO_SUCH_KEY (см. рис. 8.3).

Рис. 8.3. Иллюстрация массива сегментов

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

Анализ структуры массива сегментов

При использовании уникальных ключей проблема противоречий отсутствует, а поиск, ввод и удаление в хеш-таблице будут выполняться максимально за 0(1) времени. Это достаточно обнадеживающе, но имеются два больших недостатка. Первый состоит в том, что хеш-таблица занимает пространство Q(TV), которое вовсе не обязательно соответствует количеству объектов п, действительно присутствующих в словаре. В самом деле, если N больше п, то подобная реализация — это излишние затраты места. Вторым недостатком является требование того, чтобы ключи были уникальными целыми числами в пределах [О, N- 1], что не всегда возможно. Поскольку оба эти недостатка широко распространены, будем считать, что структура данных хеш-таблицы состоит из массива сегментов и хорошо исследованного механизма отображения (mapping) ключей с помощью целых чисел в пределах [О, N- 1].

Хеш-функции

Вторым компонентом структуры хеш-таблицы является функция h, известная как хеш-функция (hash Junction), которая ставит в соответствие каждому ключу к целое число в пределах [О, TV— 1], где N — объем (вместимость) массива сегментов рассматриваемой таблицы. При наличии такой функции можно применять метод массива сегментов к произвольным ключам. Основная идея этого подхода заключается в использовании значения хеш-функции h(k) в качестве индекса в массиве сегментов А вместо ключа к (который в большинстве случаев не удовлетворяет требованиям использования в таком массиве). То есть объект (к,е) хранится в сегменте A[h{k)].

Хеш-функцию будем называть «хорошей» или «нормальной», если она прописывает ключи в словаре таким образом, чтобы свести количество противоречий к минимуму. Из практических соображений желательно, чтобы процесс определения значения хеш-функции был быстрым и легко вычисляемым. В Java существует следующее соглашение. Определение значения хеш-функции h(k) будем рассматривать как комбинацию двух действий — отображение ключа к с помощью целого числа, известного как хеш-код (hash code), и отображение хеш-кода в виде’целого числа в пределах индексов массива сегментов, известное как преобразовательное отображение (compression тар) (рис. 8.4).

Хеш-коды

Первое действие хеш-функции — преобразование произвольного ключа к из словаря в целочисленное значение. Целое число, отображающее ключ к, называется хеш-кодом, или хеш-значением (hash value) к. Это

Рис. 8.4. Две составляющие хеш-функции: хеш-код и сжатое отображение

целочисленное значение необязательно должно входить в диапазон [О, N- 1] и даже может быть отрицательным, но задача состоит в том, чтобы, насколько это возможно, хеш-коды ключей не повторялись, то есть избежать противоречий. Кроме того, чтобы быть последовательными, хеш-код, используемый для ключа к, должен быть таким же, как и хеш-код для любого другого ключа, равного к (как это предписывается определителем равенства для словаря).

Хеш-коды в Java

Стандартный класс Object в Java по умолчанию имеет метод с защитой от повторения hashCode() для отображения каждого экземпляра объекта с помощью целого числа, являющегося «представлением» данного объекта. В частности, метод hashCode() возвращает 32-битное целое число типа int. Если метод специально не переопределялся, он наследуется каждым объектом, применяемым в Java-nporpaMMe. Но тем не менее следует принимать соответствующие меры предосторожности лри использовании стандартной версии метода hashCode() класса Object, поскольку он может оказаться всего лишь целочисленной интерпретацией места расположения объекта в памяти (как это происходит во многих Java-приложениях). Такой тип хеш-кода не справляется, например, с символьными строками, так как два различных строковых объекта в памяти в принципе могут быть равными, а значит, им может быть присвоен одинаковый хеш-код. На самом деле Java-icnacc String переопределяет метод hashCode из класса Object так, чтобы он мог работать с символьными строками. Аналогично при необходимости воспользоваться конкретными объектами в качестве ключей словаря следует переопределить встроенный метод hashCode() для этих объектов, заменив его механизмом их отображения не противоречащими друг другу целыми числами.

Теперь рассмотрим несколько распространенных типов данных и методов-примеров для отображения объектов этих типов с помощью хеш-кодов.

Приведение к целому числу

Для начала заметим, что для любого типа данных X, представленных с помощью такого же количества бит, что и используемые хеш-коды, в качестве хеш-кода для X можно просто взять целочисленное представление составляющих его бит. Таким образом, для основных типов Java — byte, short, int и char — можно получить нормальные хеш-коды путем их приведения к int. Точно так же переменную х основного типа float можно конвертировать в целое число с помощью метода Float.flоatToIntВits(x), а затем использовать его как хеш-код х.

Суммирующие компоненты

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

static int hashCode(long i) { return (int) ((i » 32) + (int)i); }

В самом деле, такой подход можно применять к любому объекту х, чье бинарное представление может рассматриваться как Ажортеж (xq, х\,

целых чисел, чтобы иметь возможность создания хеш-кода для х

к-]

как ]Г х,. Например, для любого числа с плавающей точкой можно про-

,=о

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

Полиномиальные хеш-коды

Суммарный хеш-код, описанный выше, не применим к символьным строкам или другим объектам разной длины, которые могут рассматриваться как кортежи в виде (xq, х\, -ty-i), где существенным является порядок объектов х/. Например, рассмотрим хеш-код для символьной строки 5, суммирующий значения символов ASCII (или Unicode) из s. Такой хеш-код, к сожалению, является источником большого количества нежелательных противоречий для стандартных групп строк. В частности, применение суммарного хеш-кода приводит к тому, что «tempOl» конфликтует с «templO». То же происходит и со строками «stop», «pots» и «spot». Улучшенный хеш-код должен некоторым образом принимать во внимание положение каждого X/. В альтернативном хеш-коде, который для этого и предназначен, выбирается ненулевая постоянная а* 1, и в качестве хеш-кода используется значение

Рис. 8.6. Ввод в хеш-таблицу с помощью линейного зондирования для разрешения противоречий. Здесь используется преобразующее отображение h(k) = к mod 11

Операция removeElement(A:) намного сложнее. Для полной реализации метода необходимо восстановить содержимое массива сегментов, чтобы он выглядел так, как будто объект с ключом к никогда не вводился в сегмент A[i]. Для этого требуется сдвинуть объекты к за исключением тех, у которых значение ключа и индекс сегмента совпадают. Типичным способом решения этой проблемы является замещение удаляемого объекта специальным «деактивированным объектом». Имея такой заменитель, занимающий некоторые сегменты хеш-таблицы, перенастраиваем алгоритмы removeElement(A;) или findElement(A:) так, чтобы поиск ключа к пропускал «деактивированные объекты» и продолжал зондирование до тех пор, пока не обнаружится объект с ключом к или свободный сегмент. А алгоритм insertItem(A;,e) должен остановиться на «деактивированном объекте» и заменить его новым.

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

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

Еще одной стратегией открытой адресации является квадратичное зондирование (quadraticprobing), которое интерактивно проверяет сегменты A[(i + Д/)) mod N] для У =0, 1,2, …, где /(/) = у2, до тех пор пока не найдет свободный сегмент. Как и в случае с линейным зондированием, квадратичное зондирование усложняет операцию удаления, но не применяет характерных для линейного зондирования кластерных шаблонов. При этом квадратичное зондирование создает свой вид кластеризации, известный как вторичная кластеризация (secondary clustering), когда набор заполненных ячеек «прыгает» по массиву в фиксированном порядке. Если N не было простым числом, то стратегия квадратичного зондирования может и не найти пустой сегмент в А при его наличии. В принципе,

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

Двойное хеширование

Еще одной стратегией открытой адресации, не требующей кластеризации, является двойное хеширование (double hashing). При таком подходе выбирается вторичная хеш-функция h’, и если h приписывает некоторый ключ к к уже занятому сегменту A[i], где / = h{k), происходит интерактивный переход к следующим сегментам A[{i + /(у)) mod TV] для у = 1, 2, 3, …, где /(у) = у х h'(k). В этой схеме вторичная хеш-функция не может быть равной нулю; стандартно вторичная хеш-функция определяется как h'(k) = q – {к mod q) для некоторого простого числа q < N. Здесь N также должно быть простым. Более того, вторичная хеш-функция должна выбираться таким образом, чтобы по возможности минимизировать кластеризацию.

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии