Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Чтобы вставить элемент, мы хешируем ключ элемента с целью определения номера ячейки. Затем мы просматриваем все элементы в группе, пока не обнаружим элемент, помеченный как пустой, и присваиваем его элементу, который пытаемся вставить (понятно, что в случае присутствия элемента в группе генерируется ошибка).

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

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

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

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

Контроллеры для таких устройств постоянного хранения данных, как жесткие и гибкие диски, дисководы Iomega Zip и ленточные накопители разработаны для поблочного считывания и записи данных. Обычно размер этих блоков равен какой-то степени двойки, например, 512, 1024 или 4096 байт. Поскольку контроллер должен выполнить считывание всего блока даже в том случае, когда требуется всего несколько байт, имеет смысл попытаться извлечь выгоду из подобного поведения.

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

Примером такого применения служит система пункта продажи в большом продуктовом супермаркете. В магазине могут продаваться сотни тысяч различных наименований товаров, из которых средний покупатель приобретает, скажем, не больше сотни (а то и десятка). Это идеальное применение для хеш-таблицы: каждый товар в магазине известен по его всемирному шифру продукта (UPC -Universal Product Code), т.е. 12-значному строковому значению, которое представляет собой уникальный ключ каждого товара. С учетом этого, приложение в кассовом пункте использует сканированный универсальный код товара с целью его хеширования в хеш-таблицу, а затем в запись, соответствующую товару.