Хэширование

Cтраница 2

Работа кэша показана на рис. 6.24. Поскольку в кэше хранится большое количество ( часто тысячи) блоков, требуется некий быстрый способ определения наличия или отсутствия блока в кэше. Обычно для этого используется хэширование номера устройства и дискового адреса ( номера блока) и поиск результата в хэш-табли-це. Все блоки с одинаковыми хэш-кодами сцепляются вместе в связный список. [17]

Когда следует изменять это значение. В большинстве случаев не требуется вносить какие-либо изменения: алгоритмы хэширования, предлагаемые SQL-сервером, вполне нормально работают со значениями по умолчанию. [18]

Метод, который для обеспечения быстрого поиска данных предусматривает преобразование ключей записей в адреса их размещения во внешней памяти. Основан на использовании таблиц ( хэш-таблиц), специального алгоритма хэширования [ hashing algorithm ] и функции ( хэш-функции), формирующих таблицы и реализующих поиск, а также генератора псевдослучайных чисел. [19]

Ленивые мемо-функции были введены для использования их в ленивых реализациях функциональных языков; они упрощают представление в мемо-таблицах тех аргументов, хранение которых в полном вычисленном виде больше не является необходимым. При этом устраняются многие трудности, связанные с рекурсивной проверкой на равенство и хэшированием, так что эта методика также годится и для строгих реализаций. Основная мысль заключается в смягчении тех требований, которым должна удовлетворять мемо-функция; мы скоро увидим, что все мемо-функции могут быть заданы через ленивые мемо-функции; другими словами, использование ленивой методики не приводит к потере общности. Обычные мемо-функции, которые мы будем называть полными мемо-функциями, требуются для повторного использования уже вычисленных результатов, если они применяются к аргументам, равным тем, которые были использованы накануне. [20]

Стоимость таких проверок высока, а выполняться они должны при каждом вызове мемо-функции, возможно, несколько раз по мере роста мемо-таблицы. Проблема усугубляется тем, что применение сложных методов для обработки составных структур затруднительно, например использование хэширования для оптимизации поиска в мемо-таблицах или для формирования этих таблиц в виде упорядоченных деревьев. В любом случае получение необходимой и уникальной характеризации структуры данных требует создания рекурсивной функции. Другим недостатком этого вида запоминания является то, что при проверке на равенство необходимо полное вычисление всех аргументов, и поэтому мы ограничены вычислениями аппликативного порядка. [21]

OpenPGP с поддержкой RSA-ключей до 4096 бит, алгоритмом шифрования IDEA ( 128 бит) и хэшированием MD-5. Для работы с ней вам не потребуется ничего дополнительно устанавливать. [22]

Метод грубой силы в данном случае заключается в том, чтобы оставить таблицу в том виде, в каком она есть, никак не упорядочивая элементы, и производить поиск в ней линейно от начала к концу. Если число элементов в таблице невелико ( например, не более 100), выигрыш от сортировки таблицы или применения хэширования будет невелик, но программа станет гораздо сложнее и, следовательно, вероятность содержания в ней ошибок резко возрастет. Разумеется, для функций, находящихся в критических участках системы, например в процедуре, занимающейся переключением контекста, следует предпринять все меры для их ускорения, возможно даже писать их ( Боже упаси. Но большая часть системы не находится в критическом участке. Так, ко многим системным вызовам редко обращаются. [23]

Видно, что в любом применении, в которое входит запоминание, сравнение указателей должно входить в число примитивных операций. Заметьте, что атомы также проверяются на равенство, поскольку они не имеют ассоциированного адреса; мы можем с тем же успехом считать, что каждый атом имеет уникальный ( неявный) адрес, тогда одинаковые ( равные) атомы будут идентичны согласно данному выше определению. Например, индекс хэширования может быть вычислен исходя из адреса или состояния битов указателя с помощью обычных методов. Кроме этого, подобное применение указателей для представления аргументов в мемо-таблицах облегчает сборку мусора. Мы еще встретимся с этим в разд. [24]

Во время первого прохода строится таблица символов для меток, литералов и объявляемых идентификаторов. Если символьные имена не нужно удалять во время первого прохода, то хэширование - это лучший метод. Во время второго прохода происходит порождение программы. Одни директивы выполняются при первом проходе, а другие - при втором. [25]

В последнем случае, если текущий аргумент заменяется на указатель ptr на ячейку вершины ( дерева), то применение регулировщика таблиц будет указывать, что элементы мемо-таблицы с ключами ( компонентами аргумента), равными ptr. Операция вставки не требует сканирования всей таблицы для удаления элементов, указанных регулировщиком таблиц. Достаточно лишь осуществить просмотр таблицы для обнаружения всех удаляемых элементов, применив методы хэширования или реорганизации дерева таблицы. [26]

Это может быть незамеченным для систем, работающих в пакетном режиме, но в системах реального времени и в интерактивных системах такие паузы в выполнении программы могут быть, заметны. Во-вторых, все активные ячейки просматриваются дважды ( вначале в фазе маркирования, а затем в фазе сканирования), а все мусорные - один раз ( для создания свободного списка), это приводит к росту времени исполнения. Это не вызывает затруднений в системах с реальной памятью, хотя и теряются преимущества хэширования. Однако сканирующий сборщик может обрабатывать циклические структуры данных, что является существенным требованием РО многих реализациях, например в редукции графов, при которой для осуществления рекурсии используются циклические указатели. [27]

Решение многих важных проблем требует использования больших баз данных ( БД) в реальном времени. Для выполнения заранее известного набора запросов могут быть применены предварительно организованные специальным образом данные. Для подготовки этих данных могут быть использованы средства создания адекватного запросам набора отношений базы данных, индексирования ключевых атрибутов на основе, например, хэширования или Т -, В-деревьев, предварительной сортировки, и тому подобные приемы, сокращающие время выполнения заранее известных запросов. Однако в случае порождения запросов на основе результатов уже выполненных запросов, что имеет место в современных системах поддержки принятия решений, требуется работа с не организованными специальным образом данными. В этом случае только параллельное выполнение запросов может дать результат в приемлемое время. [28]

Система на основании ключа вычисления при помощи процедуры хэширования получает номер страницы, где должна быть размещена запись, и затем ищет запись внутри страницы. Если при размещении записи для нее не оказалось места на странице, она помещается на страницу переполнения. Таким образом, при хорошем распределении записей для поиска по ключам вычисления требуется одно обращение к диску на одну запись; при наличии переполнения время может резко возрасти. Для сокращения времени следует принять такие меры, как использование более эффективной процедуры хэширования или увеличение запаса емкости ( размер файла и / или размер страницы) для учета неравномерного распределения записей. При последовательном чтении записей по диапазону страниц требуется столько обращений, сколько страниц входит в диапазон. При этом время обращения сокращается за счет более быстрого подвода головок, так как страницы читаются последовательно. [29]

Страницы: 1 2