Функция - хеширование
Cтраница 1
Функция хеширования вычисляется определенным образом. Полученное целое делится на число участков. Остаток от деления принимается за значение функции. [1]
Поиск функции хеширования - сложный и специализированный процесс, и мы не можем рассмотреть его здесь подробно. Чтобы успешно подобрать функцию хеширования, нужны глубокие познания в области статистики и лингвистики. [2]
 |
Хешированный файл. [3] |
Это - неудачная функция хеширования для названий, длина которых имеет тенденцию скапливаться вблизи 11 - 13 литер, поэтому не будет обеспечиваться равномерное заполнение участков. [4]
Как и в примере с названиями динозавров, такая функция хеширования является, вероятно, неадекватной для названий отделов, но используется здесь для простоты изложения. [5]
Программа FCOLS-0 входит в состав СКЗИ Верба-0, разработанной в Пензенской НИЭИ, обеспечивает шифрование / расшифрование информации, формирование и проверку электронной цифровой подписи, а также функцию хеширования. [6]
Поиск функции хеширования - сложный и специализированный процесс, и мы не можем рассмотреть его здесь подробно. Чтобы успешно подобрать функцию хеширования, нужны глубокие познания в области статистики и лингвистики. [7]
 |
Квадратичная проверка. [8] |
Предположим, что при вставке в хеш-таблицу элемент отображается в кластер, сформированный другими элементами. Если элемент отображается на позицию возле начала кластера, то возникнетне сколько конфликтных ситуаций, прежде чем найдется пустая ячейка для этого элемента. Поскольку параметр Рв функции хеширования растет, значение этой функции изменяется очень быстро. Это означает, что конечное положение элемента, возможно, и не будет смежным сданным кластером. [9]
Существо метода заключается в том, что мы принимаем все поля за ключ, хотя некоторое подмножество полей действительно может служить ключом, и хешируем записи, используя полное множество полей как ключ. Применив теперь обычную функцию хеширования, мы могли бы определить участок, к которому относится запись, при условии, что она нам в точности известна. Однако при более тщательном конструировании функции хеширования можно ограничивать число участков, где должны находиться соответствующие записи, всякий раз, когда известно значение одного или более полей. Хитрость состоит в разбиении битов номера участка на несколько частей таким образом, чтобы каждое поле определяло одну из частей. [10]
Часто задаются запросы, в которых специфицированы значения двух или более полей, но так, что эти поля еще не образуют полного ключа. Ниже описываются два метода решения этой задачи. Первый основан на применении множественных вторичных индексов, а второй - на специальной форме функции хеширования. Поскольку эта задача предусматривает нахождение частично специфицированных записей, она известна как задача поиска по частичному соответствию. [11]
В нескольких книгах по структурам данных рассматриваются проблемы обслуживания таблиц информации. В томе 1 этой книги ( 1968) рассмотрены структуры данных: в томе 3 ( 1973 г.) очень подробно обсуждается техника поиска, включен раздел, посвященный функциям хеширования. [12]
Каждая из операций поиска, модификации, включения и удаления требует одного доступа к внешней памяти для получения нужного блока справочника участков ( в предположении, что справочник не содержится в основной памяти), а также доступов для просмотра участка, число которых не превышает число блоков в участке. В процессе поиска записи должна быть просмотрена в среднем половина блоков. При выполнении любой операции, отличной от поиска, кроме того, необходимо снова записать модифицированный блок во внешнюю память. Если каждый участок состоит в среднем из одного блока ( это лучшее, на что можно было бы надеяться), требуется два ( для поиска) или три ( для других операций) доступа, независимо от размера файла. Чтобы уменьшить число блоков в участках, количество последних должно быть приблизительно равно числу записей в файле, деленному на число записей, которые могут быть помещены в один блок. На практике файл обычно постоянно растет. Поэтому необходимо иногда осуществлять его реорганизацию, изменяя функцию хеширования и увеличивая размер справочника участков. [13]
 |
Организация индексов в виде В-деревьев позволяет лучше использовать поверхность диска и обеспечивает более быстрый поиск, чем ISAM. [14] |
Сегодня, когда специалисты употребляют этот термин, они большей частью имеют в виду многоуровневый метод индексирования с использованием записей постоянной длины. Мы можем рассматривать первый, второй и третий уровни как индексы к четвертому уровню, применение которых существенно ускоряет поиск интересующей нас записи. Поскольку небольшое число записей на верхнем уровне связывается со множеством записей на нижнем уровне, такая организация данных называется деревом, хотя оно изображается в перевернутом виде. От каждой записи отходят воображаемые ветви, образуя узел дерева. Такой метод организации индекса не является самым гибким и эффективным. В реальной базе данных нам потребуются не все возможные 10000 кодовых обозначений - часть места будет потрачена впустую. С другой стороны, функция хеширования способна породить миллионы кодовых обозначений, и только часть из них будет использована. Таким путем невозможно обеспечить место для хранения всех записей, полученных по алгоритму хеширования. [15]
Страницы: 1