Разрешение коллизий - Динамическое хеширование
Составление хеш-функции - это не вся работа, которую предстоит выполнить программисту, реализующему поиск на основе хеширования. Кроме этого, необходимо реализовать механизм разрешения коллизий. Как и с хеш-функциями существует несколько возможных вариантов, которые имеют свои достоинства и недостатки.
Метод цепочек
Метод цепочек - самый очевидный путь решения проблемы. В случае, когда элемент таблицы с индексом, который вернула хеш-функция, уже занят, к нему присоединяется связный список. Таким образом, если для нескольких различных значений ключа возвращается одинаковое значение хеш-функции, то по этому адресу находится указатель на связанный список, который содержит все значения. Поиск в этом списке осуществляется простым перебором, т. к. при грамотном выборе хеш-функции любой из списков оказывается достаточно коротким. Но даже здесь возможна дополнительная оптимизация. Дональд Кнут ([3], стр. 558) отмечает, что возможна сортировка списков по времени обращения к элементам. С другой стороны, для повышения быстродействия желательны большие размеры таблицы, но это приведет к ненужной трате памяти на заведомо пустые элементы. На рисунке ниже показана структура хеш-таблицы и образование цепочек при возникновении коллизий.
Прекрасная наглядная иллюстрация этой схемы разрешения коллизий в виде Java-апплета вместе с исходным кодом на C++ представлена по адресу [14].
Открытая адресация
Другой путь решения проблемы, связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок, просто просматривая различные записи таблицы по порядку до тех пор, пока не будет найден ключ K или пустая позиция [3]. Идея заключается в формулировании правила, согласно которому по данному ключу определяется "пробная последовательность", т. е. последовательность позиций таблицы, которые должны быть просмотрены при вставке или поиске ключа K. Если при поиске встречается пустая ячейка, то можно сделать вывод, что K в таблице отсутствует, т. к. эта ячейка была бы занята при вставке, т. к. алгоритм проходил ту же самую цепочку. Этот общий класс методов назван открытой адресацией [4].
Похожие статьи
-
Расширяемое хеширование (extendible hashing) - Динамическое хеширование
Расширяемое хеширование близко к динамическому. Этот метод также предусматривает изменение размеров блоков по мере роста базы данных, но это...
-
Разрешение коллизии с помощью области переполнения - Проблема организации и хранения данных
При выборе этой стратегии область хранения разбивается на две части: основную область и область переполнения. Для каждой новой записи вычисляется...
-
Введение - Динамическое хеширование
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь),...
-
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляются два указателя: указатель на предыдущую запись в...
-
Рисунок 12.1 - График зависимости угловых скоростей звеньев от времени Рисунок 12.2 - График зависимости моментов в упругих звеньях от времени Из рисунка...
-
Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...
-
Кодирование цвета Кодируется цвет графических изображений с помощью бит. Количество бит, с помощью которых закодирован цвет называют битовой глубиной...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ - Программирование, ориентированное на объекты
Связанная организация памяти. - Ассоциативные структуры. - Списки. - Очереди. - Рекурсивные структуры. - Наборы. - Деревья. Связанная организация памяти...
-
Собственными называют периодические колебания консервативной системы, совершающиеся исключительно под воздействием инерционных и упругих сил. Для...
-
Задание - Четырехмассовая динамическая модель трансмиссии автомобиля
Рассчитать скорости масс и моменты в упругих звеньях трансмиссии при трогании автомобиля с места. Рисунок 1.1 - Динамическая модель Исходные данные для...
-
Узел "Конфигурация Windows" в основном предназначен для обеспечения безопасности компьютера и учетной записи, для которой применяются данные политики. В...
-
КР580ИР82 представляет собой 8-разрядный буферный регистр, предназначенный для ввода и вывода информации со стробированием. Микросхема имеет восемь...
-
Необходимо решить систему: Для решения на компьютере примем: , Решая эту систему, получаем в качестве выходных параметров скорости масс, для получения...
-
В микросхемах памяти динамического типа функции ЭП выполняет электрический конденсатор, образованный внутри МДП структуры. Информация представляется в...
-
Объект ориентированный класс программирование Цель Работы - изучить методику создания одномерных динамических символьных массивов при помощи...
-
Разработка динамических библиотек
Лекция №42. Разработка динамических библиотек Содержание: Создание собственной DLL Вызов функций из DLL Загрузка DLL с неявной компоновкой Загрузка DLL с...
-
Составление частотного уравнения методом последовательного расщепления Рисунок 3.1 - Исходная модель. Расщепим ее на массе 2 Рисунок 3.2 - Расщепление на...
-
Разрешение печатного изображения и понятие линеатуры - Растровая графика
Размер точки растрового изображения как на твердой копии (бумага, пленка и т. д.), так и на экране зависит от примененного метода и параметров...
-
Характеристики ЖК мониторов., Виды ЖК мониторов., Разрешение монитора. - ЖК-мониторы
Виды ЖК мониторов. Существует два вида ЖК мониторов: DSTN (dual-scan twisted nematic - кристаллические экраны с двойным сканированием) и TFT (thin film...
-
Расширим построенную в предыдущей главе статичную модель за счет кросс-временных взаимозависимостей из пункта 2.3. Для этого построим системы правил...
-
Создание Web-страниц в прикладной программе FrontPage - Создание сайта
Создание новой пустой Web-страницы Если при открытии окна программы FrontPage в нем отображается пустая страница, то разработку веб - страницы можно...
-
Моделирование сетей DBN Как было показано выше ряд выделенных факторов оценки деятельности образовательной организации демонстрируют взаимозависимости,...
-
Изображения в программе Adobe Photoshop CS6, Пиксели, Разрешение, Размер файла - Adobe Photoshop CS6
Пиксели Любое изображение в программе Photoshop является растровым, независимо от того, было ли оно отсканировано, импортировано из другого приложения...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
Создание простого отчета - Информационные технологии в юридической деятельности
В Access можно создавать самые разные отчеты -- от простых до сложных. Но независимо от того, какой отчет создается, действуют определенные правила....
-
Для решения трехмерной задачи упругости с помощью метода конечных элементов были заданы следующие основные параметры: [1]. Количество секций. [2]....
-
Решение задачи, Анализ оптимального решения - Использование методов линейного программирования
1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно "Параметры поиска решения" (рис.4). В этом окне оставьте...
-
Емкость, бит -16К x 1 Время цикла записи считывания - 370нс Напряжение питания - 5В,12В,-12В Потребляемая мощность: в режиме хранения - 40 мВт В режиме...
-
Пересечение луча с поверхностью - Моделирование эффектов
Алгоритм расчета пересечения луча с ограниченной поверхностью, представленный на рис.1 имеет следующие шаги: Рисунок 1 Шаг 1. Рассчитываются все точки...
-
Идентификация моделей динамических систем - ПИД-контроллеры фирмы Honeywell
Для выполнения качественного регулирования необходимы знания о динамическом поведении объекта управления. Процесс получения (синтеза) математического...
-
Построение модели предметной области с помощью описания структур данных и программного кода является классическим подходом в разработке ИС. Зачастую...
-
Для лучшего понимания динамики модели и наблюдения за процессами, в AnyLogic можно строить анимированные изображения, состоящие из динамических...
-
Структура SQL - Банки и базы данных. Системы управления базами данных
Широкое развитие информационных систем и связанная с этим унифицированность информационного пространства привело к необходимости создания стандартного...
-
В основе алгоритма лежит численное исследование пространства управляемых параметров редуктора. Процесс поиска оптимального решения выполняется за четыре...
-
Постановка задачи Постановка практической задачи ЛП включает следующие основные этапы: - определение показателя эффективности, переменных задачи, -...
-
Физические модели БД - Банки и базы данных. Системы управления базами данных
Под физической моделью БД понимается способ размещения данных на устройствах внешней памяти и способ доступа к этим данным. Каждая СУБД по-разному...
-
Введение - Транспортная задача линейного проектирования
В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Квадрат Полибия, Шифр Гронсфельда - Установка программ шифрования
Применительно к современному латинскому алфавиту из 26 букв шифрование по этому квадрату заключалось в следующем. В квадрат размером 5x6 клеток...
Разрешение коллизий - Динамическое хеширование