Удаление элементов хеш-таблицы - Динамическое хеширование
Многие программисты настолько слепо верят в алгоритмы, что даже не пытаются задумываться над тем, как они работают. Для них неприятным сюрпризом становится то, что очевидный способ удаления записей из хеш-таблицы не работает. Например, если удалить ключ, который находится в цепочке, по которой идет алгоритм поиска, использующий открытую адресацию, то все последующие элементы будут потеряны, т. к. алгоритм производит поиск до первого незанятого элемента.
Вообще говоря, обрабатывать удаление можно, помечая элемент как удаленный, а не как пустой. Таким образом, каждая ячейка в таблице будет содержать уже одно из трех значений: пустая, занятая, удаленная. При поиске удаленные элементы будут трактоваться как занятые, а при вставке - как пустые, соответственно.
Однако, очевидно, что такой метод работает только при редких удалениях, поскольку однажды занятая позиция больше никогда не сможет стать свободной, а, значит, после длинной последовательности вставок и удалений все свободные позиции исчезнут, а при неудачном поиске будет требоваться М проверок (где М, напомним, размер хеш-таблицы). Это будет достаточно долгий процесс, так как на каждом шаге №4 алгоритма поиска (см. раздел Адресация с двойным хешированием) будет проверяться значение переменной i.
Рассмотрим алгоритм удаления элемента i при линейной адресации.
- 1. Пометить TABLE[i] как пустую ячейку и установить j = i 2. i = i - 1 или i = i + M, если i стало отрицательным 3. Если TABLE[i] пуст, алгоритм завершается, т. к. нет больше элементов, о доступе к которым следует заботиться. В противном случае мы устанавливаем r = h(KEY[i]), где KEY[i] - ключ, который хранится в TABLE[i]. Это нам даст его первоначальный хеш-адрес. Если i ? r < j или если r < j < i либо j < i ? r (другими словами, если r циклически лежит между этими двумя переменным, что говорит о том, что этот элемент находится в цепочке, звено которой мы удалили выше), вернуться на шаг 1. 4. надо переместить запись table[j] = table[i] и вернуться на первый шаг.
Можно показать ([3], стр. 570), что этот алгоритм не вызывает снижения производительности. Однако, корректность алгоритма сильно зависит от того факта, что используется линейное исследование хеш-таблицы, поэтому аналогичный алгоритм для двойного хеширования отсутствует.
Данный алгоритм позволяет перемещать некоторые элементы таблицы, что может оказаться нежелательно (например, если имеются ссылки извне на элементы хеш-таблицы). Другой подход к проблеме удаления основывается на адаптировании некоторых идей, использующихся при сборке мусора: можно хранить количество ссылок с каждым ключом, говорящим о том, как много других ключей сталкивается с ним. Тогда при обнулении счетчика можно преобразовывать такие ячейки в пустые. Некоторые другие методы удаления, позволяющие избежать перемещения в таблице и работающие с любой хеш-технологией, были предложены в [16].
Похожие статьи
-
Разрешение коллизий - Динамическое хеширование
Составление хеш-функции - это не вся работа, которую предстоит выполнить программисту, реализующему поиск на основе хеширования. Кроме этого, необходимо...
-
Расширяемое хеширование (extendible hashing) - Динамическое хеширование
Расширяемое хеширование близко к динамическому. Этот метод также предусматривает изменение размеров блоков по мере роста базы данных, но это...
-
Введение - Динамическое хеширование
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь),...
-
Запрос на удаление используется, когда необходимо удалить из базы данных записи целиком, вместе со значением ключа, которое делает эти записи...
-
Понятие о массивах В ранжированных переменных невозможно использование их отдельных значений. При необходимости иметь доступ к каждому значению...
-
Создание Web-страниц в прикладной программе FrontPage - Создание сайта
Создание новой пустой Web-страницы Если при открытии окна программы FrontPage в нем отображается пустая страница, то разработку веб - страницы можно...
-
С помощью запроса на обновление можно добавлять, изменять или удалять данные в одной или нескольких записях. Запросы на обновление можно рассматривать...
-
Для решения трехмерной задачи упругости с помощью метода конечных элементов были заданы следующие основные параметры: [1]. Количество секций. [2]....
-
Описание основных возможностей МКЭ МКЭ представляет собой эффективный метод решения инженерных задач. Область применения метода от анализа напряжений в...
-
Устойчивость элементов и устройств к внешним воздействиям. Характеристики климатических воздействий. Механическая прочность. Радиационная стойкость...
-
Для реализации устройства управления потребуются: генератор слов, логические элементы (И, ИЛИ, НЕ), счетчики и логический анализатор. Ниже приведены...
-
Анализ последствий в СУ при потере проводимости клапанов элементов - Э7 - элемент находится в модуле ЗИП для ИМ1 движение вперед. В режиме ДУ сигнал для...
-
Конечно-элементный анализ широко применяется при решении задач механики деформируемого твердого тела, теплообмена, гидро - и газодинамики, электро - и...
-
Запросы - Разработка информационной системы "Гостиница"
Одним из семи стандартных объектов Microsoft Access является запрос. Запросы используются для просмотра, анализа и изменения данных в одной или...
-
Назначение и состав платы КОВ. Плата коммутации и отключения видеосигналов за пределами рабочей части экрана (КОВ) предназначена для коммутации...
-
Существуют две группы определений ОС: "совокупность программ, управляющих оборудованием" и "совокупность программ, управляющих другими программами". Обе...
-
Ввод элементов векторов и матриц - Массивы, векторы и матрицы
Векторы и матрицы можно задавать путем ввода их элементов - индексированных переменных. Для указания подстрочных индексов после имени переменной вводится...
-
Типы конечных элементов - Программное обеспечение расчета конструкций
Простейшим среди элементов является одномерный элемент. Схематически он обычно изображается в виде отрезка, хотя и имеет поперечное сечение. Площадь...
-
Рассмотрим особенности программирования под Android. Класс Activity - самый важный класс, из которого строится приложение Android. Этот класс...
-
Общее понятие о методе конечных элементов - Алгоритмы компьютерного моделирования
Метод конечных элементов заключается в разбиении математической модели конструкции некоторые элементы, называемые конечными элементами. Элементы бывают...
-
Механизмы обеспечения безопасности, Криптография - Защита информации в компьютерных сетях
Криптография Для обеспечения секретности применяется шифрование, или криптография, позволяющая трансформировать данные в зашифрованную форму, из которой...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
Элементы теории графов. Сеть Петри. Конечный автомат
Вариант №8 Задача 1. Элементы теории графов Связный ориентированный граф G(Х, Г) задан множеством вершин X={x1, x2, ..., xn} и отображением Гxi={x|Ik|,...
-
Элементы и устройства автоматики
2 лекция. Типовые структуры и средства АСУ ТП. Локальные системы контроля, регулирования и управления. Автоматизированные системы управления...
-
Уже пакетный режим в своем развитом варианте требует разделения процессорного времени между выполнением нескольких программ. Необходимость в разделении...
-
Поиск и замена текста При работе с длинными документами иногда приходится вносить в них повторяющиеся изменения. ПрограммаWriterимеет специальные...
-
Для реализации поставленной задачи методом конечных элементов будут использованы следующие программные обеспечения (ПО): - MATLAB - ПО и одноименный язык...
-
Встроенный оптимизатор запросов в Teradata может значительно ускорить запрос по сравнению тем, как если бы команды выполнялись ровно так, как подает...
-
Емкость, бит -16К x 1 Время цикла записи считывания - 370нс Напряжение питания - 5В,12В,-12В Потребляемая мощность: в режиме хранения - 40 мВт В режиме...
-
Элементы самодвойственных сетей - Функциональные модели универсального нейрокомпьютера
Если при обратном функционировании самодвойственной сети на ее выход подать производные некоторой функции F по выходным сигналам сети, то в ходе...
-
Разработка форм - Разработка базы данных "Кинопрокат" В СУБД MS Access
Формы - одно из основных средств для работы с базами данных в Access - используются для ввода новых записей (строк таблиц), просмотра и редактирования...
-
Впервые последовательное описание конструирования нейронных с Етей из элементов было предложено в книге А. Н. Горбаня [65]. Однако за прошедшее время...
-
На добавление Создадим запрос на добавление для формы "Режиссеры". На вкладке "СОЗДАНИЕ" жмем "Конструктор запросов", тип запроса выбираем "Добавление"....
-
КР580ИР82 представляет собой 8-разрядный буферный регистр, предназначенный для ввода и вывода информации со стробированием. Микросхема имеет восемь...
-
В микросхемах памяти динамического типа функции ЭП выполняет электрический конденсатор, образованный внутри МДП структуры. Информация представляется в...
-
Расширим построенную в предыдущей главе статичную модель за счет кросс-временных взаимозависимостей из пункта 2.3. Для этого построим системы правил...
-
Обозначение элементов моделирования При экспресс-анализе для описания бизнес-процессов и построении их моделей, использовался программный продукт...
-
Запуск Snort - Инструменты безопасности с открытым исходным кодом. Системы обнаружения вторжений
Snort запускается из командной строки. Его можно выполнять в трех различных режимах: анализа, протоколирования и обнаружения вторжений. Последний режим...
-
В рамках каждого рабочего пространства может быть создано неограниченное количество проектов. При выборе проекта отображается список задач по нему,...
-
Кодированием называется представление символов одного алфавита средствами другого алфавита. Алфавит содержащий два символа называется двоичным (часто их...
Удаление элементов хеш-таблицы - Динамическое хеширование