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

0

Фрагменты кода 8.1—8.2 иллюстрируют большую часть класса LinearProbingHashTable, реализующего АТД «словарь» с применением хеш-таблицы и линейного зондирования для разрешения противоречий. Этот отрывок кода включает основные методы словаря (остальное — в упражнении М-8.9).

Основными элементами дизайна Java-класса LinearProbingHashTable являются следующие.

isEqualTo(A:b/:2) (проверяющий равенство двух ключей) и hashValue (к) (возвращающий хеш-функцию ключа).

Определяется сигнальное сообщение AVAILABLE в качестве метки деактивированных объектов.

Для конструкторов предоставляются хеш-компаратор и (по желанию) целое число, указывающее размерность массива сегментов. Если количество объектов п равно размерности массива N, то при попытке ввода нового объекта генерируется исключение Hash- TableFullException.

Используются следующие вспомогательные методы:

?         available(z’), проверяющий, ссылается ли A[i] на метку AVAILABLE;

?         empty(/), проверяющий, является ли A[i] пустым;"

?         кеу(/), возвращающий ключ объекта из A[i]\

?         element(/), возвращающий элемент из A[i];

?         check(A;), проверяющий, можно ли сравнивать ключ к с помощью хеш-компаратора, и выдающий сообщение об исключении InvalidKeyException при невозможности сравнения.

public class LinearProbingHashTable implements Dictionary {

/** маркер для деактивированных сегментов [20]/

private static Item AVAILABLE = new ltem(null, null);

/** количество объектов в словаре */

private int n = 0;

/** объем массива сегментов */

private int N;

/** массив сегментов */

private ltem[ ] A;

/** хеш-компаратор */

private HashComparator h;

/** конструктор хеш-компаратора */ public LinearProbingHashTable(HashComparator he) { h = he;

N = 1023; // объем, выставленный по умолчанию А = new ltem[JM];

}

/** конструктор хеш-компаратора и объема массива сегментов */ public LinearProbingHashTable(HashComparator he, int ЫМ) { h = he; N = bN;

A = new ltem[N];

}

// вспомогательные методы

private boolean available(int i) { return (A[i] == AVAILABLE); } private boolean efnpty(int i) { return (A[i] == null); } private Object key(int i) { return A[i].key(); } private Object element(int i) { return A[i].element(); } private void check(Object k) { if (!h.isComparable(l^)

throw new lnvalidKeyException(«Неверный ключ.»);

}

Фрагмент кода 8.1. Часть класса LinearProbingHashTable, реализующего АТД «словарь» с применением хеш-таблицы и линейного зондирования для разрешения противоречий (продолжение — фрагмент кода 8.2)

/** вспомогательный метод поиска */ private int findltem(Object key) throws InvalidKeyException { check(key);

int i = h.hashValue(key) % N; // механизм приведения метода деления int j = i; do {

if (empty(i)) return -1; // объект не найден if (available(i)) i = (i + 1) % N; // сегмент деактивирован else if (h.isEqualTo(key(i), key)) // наш объект найден

return i; else // поиск продолжается i = (i + 1) % N; } while (i != j);

return -1; // объект не найден

}

// методы АТД «словарь»

public Object findElement (Object key) throws InvalidKeyException { int i = findltem(key); // вспомогательный метод для поиска ключа if (i < 0) return Dictionary.NO_SUCH_KEY; return element(i);

}

public void insertltem (Object key, Object element) throws InvalidKeyException { check(key);

int i = h.hashValue(key) % N; // механизм приведения метода деления int j = i; // вернуться к началу do {

if (empty(i) I available(i)) { // этот сегмент доступен A[i] = new ltem(key, element); n++; return;

i = (i + 1) % N; // проверить следующий сегмент } while (i != j); II повторять до тех пор, пока не вернемся к началу throw new HashTableFullException("Xem-Ta6nHua заполнена.");

public Object removeElement (Object key) throws InvalidKeyException { int i = findltem(key); // вначале найти этот ключ if (i <0) return Dictionary.NO-SUCH-KEY; // удалять нечего Object toReturn = element(i);

A[i] = AVAILABLE; // отметить данный сегмент как деактивированный п—;

return toReturn;

}

Фрагмент кода 8.2. Часть класса LinearProbingHashTable, реализующего АТД «словарь» с применением хеш-таблицы и линейного зондирования для разрешения противоречий (начало — фрагмент кода 8.1)

Коэффициенты нагрузки и переформатирование

Во всех вышеописанных схемах хеш-таблиц требуется, чтобы коэффициент нагрузки Х = \п / N~[не превышал 1. Эксперименты и стандартные виды анализа показывают, что для схем открытой адресации X < 0,5, а для раздельных цепей X < 0,9. И действительно, как можно убедиться, выполнив упражнение 3-8.7, некоторые схемы открытой индексации начинают срываться при X < 0,5. Хотя подробный анализ хеширования не является предметом настоящей книги, его вероятностная основа достаточно интуитивна. При использовании нормальной хеш-функции можно ожидать одинакового распределения значений хеш-функций в пределах [0, N- 1]. Таким образом, чтобы сохранить п объектов в словаре, предполагаемое количество ключей в сегменте составит |~п / N~|, что составляет 0(1), если п есть O(N).

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

С другой стороны, по мере увеличения коэффициента нагрузки X от 0,5 к 1 при работе с открытой адресацией возможность появления кластеров объектов в массиве сегментов также возрастает. Наличие кластеров при зондировании заставляет процедуры «прыгать» по массиву достаточно долго, прежде чем они смогут завершиться. При ограничении условия, когда Устремится к 1, все словарные операции имеют ожидаемое линейное время выполнения, так как в этом случае предполагается проход линейного количества-занятых сегментов, прежде чем обнаружится свободная ячейка.

Таким образом, поддержка коэффициента нагрузки ниже определенного значения жизненно важна для схем открытой адресации и немаловажна для метода раздельных цепей. Если коэффициент нагрузки значительно выше указанной величины, то будет вполне естественным изменить размер таблицы (чтобы получить нужный коэффициент) и заново ввести объекты в новую таблицу. И действительно, если позволить таблице заполниться, некоторые реализации, включая реализацию на Java из фрагмента кода 8.1, могут завершиться аварийно. При переформатировании таблицы наилучшим решением будет сразу увеличить ее размер в два раза. Как только размерность нового массива сегментов установлена, следует определить и новую хеш-функцию, работающую с ним (вероятно, просчитав новые параметры, как в MAD-методе). Имея новую хеш-функцию, с ее помощью заново вводим каждый объект из старого массива в новый. Назовем это процесс переформатированием (rehashing).

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

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

По теме:

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