Читайте также:
|
|
1. Функция называется идеальной хеш-функцией для , если она инъективна на ;
2. Функция называется минимальной идеальной хеш-функцией для , если она является ИХФ и ;
3. Для целого , функция называется -идеальной хеш-функцией (k-PHF) для если для каждого имеем .
Идеальное хеширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе. Одним из наибоее очевидных примеров использования идеального (или скорее k-идеального) хеширования является ситуация, когда мы распологаем небольшой быстрой памятью, где размещаем значения хешей, связанных с данными хранящимися в большой, но медленной памяти. Причем размер блока можно выбрать таким, что необходимые нам данные, хранящиеся в медленной памяти, будут получены за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, в тех случаях, когда представление графа не умещается в основной памяти. [5]
Дата добавления: 2014-12-23; просмотров: 18 | Поможем написать вашу работу | Нарушение авторских прав |