Хэш-функции и хэш-адресация - Хеш-функция
В реальных исходных программах количество идентификаторов столь велико, что даже логарифмическую зависимость времени поиска от их числа нельзя признать удовлетворительной. Необходимы более эффективные методы поиска информации в таблице идентификаторов. Лучших результатов можно достичь, если применить методы, связанные с использованием хэш-функций и хэш-адресации.
Хэш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) = n, r ? R, n ? Z. Сам термин "хэш-функция" происходит от английского термина <hash function" (hash - "мешать", "смешивать", "путать"). Вместо термина "хэширование" иногда используются термины "рандомизация", "переупорядочивание". Множество допустимых входных элементов R называется областью определения хэш-функции. Множеством значений хэш-функции F называется подмножество М из множества целых неотрицательных чисел Z: М, содержащее все возможные значения, возвращаемые функцией F: ? r?R: F(r) ?М. Процесс отображения области определения хэш-функции на множество значений называется "хэшированием". При работе с таблицей идентификаторов хэш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел.
Областью определения хэш-функции будет множество всех возможных имен идентификаторов.
Хэш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных. Тогда размер массива данных должен соответствовать области значений используемой хэш - функции. Следовательно, в реальном компиляторе область значений хэш-функции никак не должна превышать размер доступного адресного пространства компьютера. Метод организации таблиц идентификаторов, основанный на использовании хэш-адресации, заключается в размещении каждого элемента таблицы в ячейке, адрес которой возвращает хэш-функция, вычисленная для этого элемента. Тогда в идеальном случае для размещения любого элемента в таблице идентификаторов достаточно только вычислить его хэш-функцию и обратиться к нужной ячейке массива данных. Для поиска элемента в таблице необходимо вычислить хэш-функцию для искомого элемента и проверить, не является ли заданная ею ячейка массива пустой (если она не пуста - элемент найден, если пуста - не найден).
Первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми. Этот метод весьма эффективен, поскольку как время размещения элемента в таблице, так и время его поиска определяются только временем, затрачиваемым на вычисление хэш-функции, которое в общем случае несопоставимо меньше времени, необходимого для многократных сравнений элементов таблицы. Метод имеет два очевидных недостатка. Первый из них - неэффективное использование объема памяти под таблицу идентификаторов: размер массива для ее хранения должен соответствовать всей области значений хэш-функции, в то время как реально хранимых в таблице идентификаторов может быть существенно меньше. Второй недостаток - необходимость соответствующего разумного выбора хэш-функции. Этот недостаток является настолько существенным, что не позволяет непосредственно использовать хэш-адресацию для организации таблиц идентификаторов. Проблема выбора хэш-функции не имеет универсального решения. Хэширование обычно происходит за счет выполнения над цепочкой символов некоторых простых арифметических и логических операций. Самой простой хэш-функцией для символа является код внутреннего представления в компьютере литеры символа. Эту хэш-функцию можно использовать и для цепочки символов, выбирая первый символ в цепочке. Очевидно, что такая примитивная хэш-функция будет неудовлетворительной: при ее использовании возникнет проблема - двум различным идентификаторам, начинающимся с одной и той же буквы, будет соответствовать одно и то же значение хэш-функции. Тогда при хэш-адресации в одну и ту же ячейку таблицы идентификаторов должны быть помещены два различных идентификатора, что явно невозможно. Такая ситуация, когда двум или более идентификаторам соответствует одно и то же значение хэш-функции, называется коллизией. Естественно, что хэш-функция, допускающая коллизии, не может быть использована для хэш-адресации в таблице идентификаторов. Причем достаточно получить хотя бы один случай коллизии на всем множестве идентификаторов, чтобы такой хэш-функцией нельзя было пользоваться. Но возможно ли построить хэш-функцию, которая бы полностью исключала возникновение коллизий? Для полного исключения коллизий хэш-функция должна быть взаимно однозначной: каждому элементу из области определения хэш-функции должно соответствовать одно значение из ее множества значений, и наоборот - каждому значению из множества значений этой функции должен соответствовать только один элемент из ее области определения. Тогда любым двум произвольным элементам из области определения хэш-функции будут всегда соответствовать два различных ее значения. Теоретически для идентификаторов такую хэш-функцию построить можно, так как и область определения хэш-функции (все возможные имена идентификаторов), и область ее значений (целые неотрицательные числа) являются бесконечными счетными множествами, поэтому можно организовать взаимно однозначное отображение одного множества на другое. Но на практике существует ограничение, делающее создание взаимно однозначной хэш-функции для идентификаторов невозможным. Дело в том, что в реальности область значений любой хэш-функции ограничена размером доступного адресного пространства компьютера. Множество адресов любого компьютера с традиционной архитектурой может быть велико, но всегда конечно, то есть ограничено. Организовать взаимно однозначное отображение бесконечного множества на конечное даже теоретически невозможно. Можно, конечно, учесть, что длина принимаемой во внимание части имени идентификатора в реальных компиляторах на практике также ограничена - обычно она лежит в пределах от 32 до 128 символов (то есть и область определения хэш-функции конечна). Но и тогда количество элементов в конечном множестве, составляющем область определения хэш-функции, будет превышать их количество в конечном множестве области ее значений (количество всех возможных идентификаторов больше количества допустимых адресов в современных компьютерах). Таким образом, создать взаимно однозначную хэш-функцию на практике невозможно. Следовательно, невозможно избежать возникновения коллизий. Поэтому нельзя организовать таблицу идентификаторов непосредственно на основе одной только хэш-адресации. Но существуют методы, позволяющие использовать хэш-функции для организации таблиц идентификаторов даже при наличии коллизий.
Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехэширования (или расстановки). Согласно этому методу, если для элемента А адрес n0 = h(А), вычисленный с помощью хэш-функции h, указывает на уже занятую ячейку, то необходимо вычислить значение функции n1 = h1(А) и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(А), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hI(А) не совпадет с h(А). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет -- выдается информация об ошибке размещения идентификатора в таблице. Тогда поиск элемента А в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму: 1. Вычислить значение хэш-функции n = h(А) для искомого элемента А.
- 2. Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке n с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= 1 и перейти к шагу 3. 3. Вычислить nI = hI(А). Если ячейка по адресу nI пустая или n = nI, то элемент не найден и алгоритм завершен, иначе -- сравнить имя элемента в ячейке nI с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= i + 1 и повторить шаг 3.
Алгоритмы размещения и поиска элемента схожи по выполняемым операциям. Поэтому они будут иметь одинаковые оценки времени, необходимого для их выполнения.
При такой организации таблиц идентификаторов в случае возникновения коллизии алгоритм помещает элементы в пустые ячейки таблицы, выбирая их определенным образом. При этом элементы могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хэш-функции, что приведет к возникновению новых, дополнительных коллизий. Таким образом, количество операций, необходимых для поиска или размещения в таблице элемента, зависит от заполненности таблицы. Для организации таблицы идентификаторов по методу рехэширования необходимо определить все хэш-функции hI для всех i. Чаще всего функции hI определяют как некоторые модификации хэш-функции h. Например, самым простым методом вычисления функции hI(А) является ее организация в виде hI(А) = (h(А) + рI) mod NM, где рI -- некоторое вычисляемое целое число, а NM -- максимальное значение из области значений хэш-функции h. В свою очередь, самым простым подходом здесь будет положить рI = i. Тогда получаем формулу hI(А) = (h(А) + i) mod NM. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции; заданной хэш-функцией h(А). Этот способ нельзя признать особенно удачным: при совпадении хэш адресов элементы в таблице начинают группироваться вокруг них, что увеличивает число необходимых сравнений при поиске и размещении. Но даже такой примитивный метод рехэширования является достаточно эффективным средством организации таблиц идентификаторов при неполном заполнении таблицы.
Похожие статьи
-
Простейшие методы построения таблиц идентификаторов - Хеш-функция
В простейшем случае таблица идентификаторов представляет собой линейный неупорядоченный список, или массив, каждая ячейка которого содержит данные о...
-
Принцип реализации СЛАУ на кластере - Администрирование параллельных процессов
Метод Гаусса - широко известный прямой алгоритм решения систем линейных уравнений, для которых матрицы коэффициентов являются плотными. Если система...
-
Разрешение коллизий - Динамическое хеширование
Составление хеш-функции - это не вся работа, которую предстоит выполнить программисту, реализующему поиск на основе хеширования. Кроме этого, необходимо...
-
Расчет диаметра сети - Проектирование учебной локальной вычислительной сети
Методика определения диаметра сети может быть оформлена в виде таблицы. Номера строк и столбцов в ней соответствуют индиентификаторам рабочих станций на...
-
Связи между таблицами - Разработка информационной системы "Гостиница"
Все ранее созданные таблицы должны быть связаны между собой каким-либо определенным полем, называемым ключевым полем. Ключевое поле позволяет однозначно...
-
Где может размещаться блок в кэш-памяти? - Компьютерные и сетевые технологии
Принципы размещения блоков в кэш-памяти определяют три основных типа их организации: Если каждый блок основной памяти имеет только одно фиксированное...
-
Даталогическое проектирование - Банки и базы данных. Системы управления базами данных
Даталогической моделью БД называется модель логического уровня, построенная в рамках конкретной СУБД, в среде которой проектируется БД. Описание...
-
В основе алгоритма лежит численное исследование пространства управляемых параметров редуктора. Процесс поиска оптимального решения выполняется за четыре...
-
Структура SQL - Банки и базы данных. Системы управления базами данных
Широкое развитие информационных систем и связанная с этим унифицированность информационного пространства привело к необходимости создания стандартного...
-
Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная...
-
Защита корпоративной информации - Защита информации
Однако при решении этой проблемы предприятия часто идут на поводу у компаний-подрядчиков, продвигающих один или несколько продуктов, решающих, как...
-
Встроенный оптимизатор запросов в Teradata может значительно ускорить запрос по сравнению тем, как если бы команды выполнялись ровно так, как подает...
-
Удаление элементов хеш-таблицы - Динамическое хеширование
Многие программисты настолько слепо верят в алгоритмы, что даже не пытаются задумываться над тем, как они работают. Для них неприятным сюрпризом...
-
Взаимодействие с проектировщиком - Программа "Кристалл" SCAD office
Во время проверки конструкции в диалоговых окнах выводится значение Кmax -- максимального (то есть наиболее опасного) из обнаруженных значений К и...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
Построение дерева - Деревья решений
Пусть нам задано некоторое множество T, содержащее объекты, каждый из которых характеризуется m атрибутами, причем один из них указывает на...
-
Теоретические вопросы - Табличный процессор MS Excel 2010
Вопрос 1 Каким образом задаются условия в диалоговом окне при использовании условного форматирования? Условное форматирование позволяет применять...
-
Цель данной работы - реализовать добавление слова в словарь на основе заданного алфавита на языке программирования высокого уровня. Основной задачей...
-
В этом разделе описаны запросы, выполняемых всеми компонентами, а также типы данных, используемые при описании запросов. Стандарт типов данных При...
-
Основы Байесовского вывода Сети Байеса Jensen, Finn An introduction to Bayesian networks. -- Berlin: Springer, 1996. -- ISBN 0-387-91502-8 - наглядный...
-
Теоретические предпосылки исследования Системы поддержки принятия решений Системы поддержки принятия решений (СППР), представляют собой приложения узкого...
-
Создание Web-страниц в прикладной программе FrontPage - Создание сайта
Создание новой пустой Web-страницы Если при открытии окна программы FrontPage в нем отображается пустая страница, то разработку веб - страницы можно...
-
CoDeSys -- универсальный инструмент разработки прикладных программ для программируемых логических контроллеров на языках стандарта IEC 61131-3. Данный...
-
Введение, Теоретические основы - Разработка консольного приложения на языке С++
Данная работа посвящена созданию своего рода базы данных на языке программирования С++. База данных содержит информацию о сотрудниках этого предприятия,...
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
Основные возможности табличного процессора MS Excel
Задание 1. Необходимо Создать Лист Для Расчета Значения Выражения При Заданных Значениях A И B 1.1. Оформляем таблицу, принимаем за a и b некоторые...
-
Введение - Вычисление максимума функции с некоторыми критериями
Если функция, определенная и непрерывная в заданном промежутке, не является в нем монотонной, то найдутся такие части этого промежутка, в которых...
-
Методология общесистемного проектирования
14 Курсовая работа По курсу Методология общесистемного проектирования Задача 1 Постановка задачи. Пусть задана универсальная схема отношений R: R = A -...
-
Выводы - Создание таблиц в Microsoft Excel
Итак, в ходе работы мною были изучены необходимые учебные материалы, а также были отработаны навыки работы с табличным процессором MS Excel 2010. Я...
-
Численные методы расчета - Алгоритмы компьютерного моделирования
Решить задачу для математической модели - значит указать алгоритм для получения требуемого результата из исходных данных. Алгоритмы решения условно...
-
Построение реляционной схемы БД - Банки и базы данных. Системы управления базами данных
В основе реляционной модели БД лежит понятие отношения. Под отношением в этой модели понимается двумерная таблица данных. Строки таблицы называются...
-
Для реализации устройства управления потребуются: генератор слов, логические элементы (И, ИЛИ, НЕ), счетчики и логический анализатор. Ниже приведены...
-
2.1 Процесс проектирования БД на основе принципов нормализации представляет собой последовательность переходов от неформального словесного описания...
-
Постановка задачи: Для заданных функций необходимо: 1. Построить электронную таблицу (одну для обеих функций) для вычисления значений функций в заданном...
-
Базы данных (БД) составляют в настоящее время основу компьютерного обеспечения информационных процессов, входящих практически во все сферы человеческой...
-
Фреймы и формы - Разработка программ на языке Ассемблер и на языке HTML
Зачастую на Web - сайтах можно встретить страницы с размещенными на них HTML - формами. Веб-формы - удобный способ получения информации от посетителей...
-
Метод конечных элементов является численным методом для нахождения приближенных решений физических задач. В основе этого метода лежит разделение...
-
При использовании этого способа данные во всех консолидируемых областях должны располагаться идентично. Для консолидации следует выполнить следующие...
-
Введение - Транспортная задача линейного проектирования
В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная...
-
Корпоративные сети. Характеристики корпоративных компьютерных сетей В зависимости от масштаба производственного подразделения, в пределах которого...
Хэш-функции и хэш-адресация - Хеш-функция