|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[75] выбор зависит от того, какого рода данные подвергаются хешированию. В книге [123] Кнут обсуждает выбор константы А и приходит к выводу, что значение является довольно удачным. В заключение приведём пример: если к = 123456, то = 10000 и А определено формулой (12.2), то 12.3.3. Универсальное хеширование Если недоброжелатель будет специально подбирать данные для хеширования, то (зная функцию h) он может устроить так, что все га ключей будут соответствовать одной позиции в таблице, в результате чего время поиска будет равно в (га). Любая фиксированная хеш-функция может быть дискредитирована таким образом. Единственный выход из положения - выбирать хеш-функцию случайным образом, не зависящим от того, какие именно данные вы хешируете. Такой подход называется универсальным хешированием (universal hashing). Что бы ни предпринимал ваш недоброжелатель, если он не имеет информации о выбранной хеш-функции, среднее время поиска останется хорошим. Основная идея универсального хеширования - выбирать хеш-функцию во время исполнения программы случайным образом из некоторого множества. Стало быть, при повторном вызове с теми же входными данными алгоритм будет работать уже по-другому. Как и в случае с алгоритмом быстрой сортировки, рандомизация гарантирует, что нельзя придумать входных данных, на которых алгоритм всегда бы работал медленно (в примере с компилятором и таблицей символов не сможет получиться, что какой-то определённый стиль выбора идентификаторов приводит к замедлению компиляции: вероятность, что компиляция замедлится из-за неудачного хеширования, во-первых, мала, и во-вторых, зависит только от количества идентификаторов, но не от их выбора). Пусть И - конечное семейство функций, отображающих данное множество U (множество всевозможных ключей) во множество {0,1,..., то - 1} (множество хеш-значений). Это семейство называется универсальным (universal), если для любых двух ключей х,у G U число функций h £ 7i, для которых h(x) = h(y), равно h(k) = [10000 • (123456 • 0,61803. = [10000- (76300,0041151... = [10000-0,0041151...] = = [41,151...] = 41. .. mod 1)J mod 1)J = \H\jm. Иными словами, при случайном выборе хеш-функции вероятность коллизии между двумя данными ключами должна равняться вероятности совпадения двух случайно выбранных хеш-значений (которая равна 1/га). Следующая теорема показывает, что универсальное семейство хеш-функций обеспечивает хорошую производительность в среднем. Теорема 12.3. Пусть нам необходимо поместить п фиксированных ключей в таблицу размера га, где га п, и хеш-функция выбирается случайным образом из универсального семейства. Тогда математическое ожидание числа коллизий, в которых участвует данный ключ х, меньше единицы. Доказательство. Математическое ожидание числа коллизий данного ключа х с данным ключом у равно 1/га по определению универсального семейства. Поскольку всего имеется п-1 ключей, отличных от х, математическое ожидание числа коллизий с каким-нибудь из этих ключей равно (п - 1)/га, что меньше единицы, поскольку п га.□ Как же построить универсальное семейство? Нам поможет в этом элементарная теория чисел. Число га (количество хеш-значений) выберем простым. Будем считать, что каждый ключ представляет собой последовательность г + 1 «байтов» (байт, или символ,- это просто двоичное число с ограниченным числом разрядов; мы будем считать, что максимальное значение байта меньше га). Для каждой последовательности а = (ао, а\,..., аг), элементы которой являются вычетами по модулю га (то есть принадлежат множеству {0,1,...,га- 1}), рассмотрим функцию ha, заданную формулой г ha(x) = djXj mod га,(12.3) 8 = 0 где ключ х есть последовательность байтов (жо, х\,..., хг). Положим П = \J{ha},(12.4) а Очевидно, множество И содержит rar+1 элементов. Теорема 12.4. Семейство функций И, определённое по формулам (12.3) и (12.4), является универсальным семейством хеш-функций. Доказательство. Пусть ж = (жо, х\,..., хг) и у = (уо, у\,..., уг) - два различных ключа; не ограничивая общности, можно считать, что жо ф уо- Если а = (ао, сц, , аг), то ha(x) = ha(y) тогда и только тогда, когда Поскольку жо - уо ф 0 (mod то), для каждой последовательности (ai,..., аг) существует и единственно значение ао, при котором это равенство выполнено (раздел 33.4). Количество таких последовательностей равно тог, и таково же, стало быть, количество функций из 7i, не различающих ключи хну. Поскольку тог = \7i\/m, всё доказано. [Короче можно сказать так: ненулевой линейный функционал h \-> h(x - у) с равной вероятностью принимает любое из то своих значений, в том числе 0.]□ Упражнения 12.3-1 Пусть в связанном списке каждый элемент хранится вместе с его ключом к и соответствующим хеш-значением h(k). Ключ представляет собой длинную последовательность символов. Как можно упростить поиск в этом списке элемента с данным ключом? 12.3-2 Предположим, что ключами являются последовательности символов, которые мы рассматриваем как числа, записанные в системе счисления с основанием 128. Число то помещается в 32-битном слове с запасом, но числа, соответствующие ключам, уже не помещаются, поскольку ключи содержат много десятков символов. Как вычислить хеш-функцию, построенную методом деления? (Нет необходимости реализовывать арифметические операции с длинными числами - достаточно дополнительной памяти постоянного объёма.) 12.3-3 Пусть ключи представляют собой последовательности р-битных символов, рассматриваемые как числа в 2р-ичной системе счисления, а в качестве хеш-функции выбран остаток при делении на то = 2Р - 1. Покажите, что двум ключам, отличающимся только порядком символов, соответствует одно и то же хеш-значение. Приведите пример приложения, в котором применение такой хеш-функции было бы нежелательно. 12.3-4 Пусть размер хеш-таблицы равен то = 1000, а хеш-функция имеет вид h(k) = [т(кА mod 1) , где А = (л/5 - 1)/2. В какие позиции попадут ключи 61, 62, 63, 64 и 65? 12.3-5 Удалим из семейства 7i, определённого по формулам (12.3) и (12.4), те функции ha, в которых хотя бы одно из аг- j = l |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||