Метода - хеширование
Cтраница 1
Методы хеширования весьма распространены в практике программирования. [1]
Второй метод хеширования предложен А. П. Ершовым [50] и называется открытой адресацией. Он предполагает наличие закольцованного массива для га записей и наличие понятия пустой записи. После этого для поступившего запроса х вычисляется значение хеш-функции / г ( ж), и если оно равно г, то просматривается с г-ой позиции массив записей пока запись х будет найдена или пока не встретится пустая запись. [2]
Второй метод хеширования предложен А. П. Ершовым [50] и называется открытой адресацией. Он предполагает наличие закольцованного массива для т записей и наличие понятия пустой записи. После этого для поступившего запроса х вычисляется значение хеш-функции h ( x), и если оно равно г, то просматривается с г-ой позиции массив записей пока запись х будет найдена или пока не встретится пустая запись. [3]
С методами хеширования связаны вместе с тем некоторые осложняющие обстоятельства. Прежде всего разные значения ключа могут давать одну и ту же свертку. Тогда при размещении не первой записи из множества записей с такими значениями ключей выделенное для записи пространство оказывается занятым другой записью. [4]
В методах хеширования, используемых для хранения множеств, в обоих способах обработки коллизий - рехешировании и последовательнрм сканировании - возникают трудности, если разрешены исключения Из множества. [5]
Обычно используется два основных метода хеширования. Думи [143] и называемый методом цепочек, предполагает наличие га списков. Если это поиск с занесением, то в случае неудачного поиска запись х добавляется к г-ому списку. [6]
Обычно используется два основных метода хеширования. Думи [143] и называемый методом цепочек, предполагает наличие т списков. Если это поиск с занесением, то в случае неудачного поиска запись х добавляется к г-ому списку. [7]
 |
Принцип метода выборочного замещения. Новые элементы из нерассортированного файла. 10, 1, 7, 20, 13, 5, 9, 15, 6, 24, 11, 26, 4 ( HP - нерассортированный, Р - рассортированный. [8] |
Примерами такого подхода являются методы хеширования, обсуждавшиеся в разд. [9]
Более того, для выполнения поиска методами хеширования всегда требуется время, пропорциональное длине ключа, поскольку требуется вычислять хеш-функцию. Однако метод patricia - деревьев позволяет обращаться непосредственно к интересуемым разрядам и, как правило, требует проверки менее IgTV из них. В связи с этим patricia - метод ( или поиск с использованием trie - дерева, из которого удалены однонаправленные ветвления) - наиболее предпочтительный метод поиска при наличии длинных ключей. [10]
Более тот, для Hwrro ( 4eHkffl поиска методами хеширования ясегда требу стен ЕЕроЕСОршюнальнйЕ XIHHC ключа, поскольку зрейуст н начислить хеш-функиию. Опнако Meroi parricisi - леревьев [ юзнсишег обрчисуться негтосредсткслно к интересуемой разря / тм ич как ира & нло, требует проверки менее Ig. И с: тим pairicia - мстод лн поиск с исио - п оваиисм ( пс - срева. ЕКТРЛСЗЗИН) - наиболее преллочтнтельный мс гад поиска при наличии длинных ключей. [11]
Если можно заранее предусмотреть количество элементов, которые должны быть помещены в хеш-таблицу, и при наличии достаточно большой непрерывной области памяти, в которой можно хранить все ключи при некотором остающемся свободном объеме памяти, в хеш-таблице, вероятно, вообще не стоит использовать какие-либо связи. Существует несколько методов хранения TV элементов в таблице размером М N, при которых разрешение конфликтов основывается на наличии пустых мест в таблице. Такие методы называются методами хеширования с открытой адресацией. [12]
Для реализации доступа к записи по методу вычисления адреса по значению первичного поискового ключа ( CALC-ключа) на каждой странице области организуются два специальных CALC-указателя. Эти указатели рассматриваются как запись - владелец экземпляра системного CALC-набора. При этом каждой странице соответствует свой экземпляр CALC-набора. При помещении записи в БД, на основании значения первичного ключа записи формируется по методу хеширования номер страницы области, затем запись размещается на этой странице и включается в CALC-набор, владелец которого находится также на этой странице. Если на странице не хватает места, то запись размещается на другой странице, однако включается в тот экземпляр CALC-набора, который находится на странице, определенной хешированием по значению ключа. При поиске записи по значению CALC-ключа СУБД с помощью хеширования определяет экземпляр CALC-набора, а затем в нем последовательным просмотром членов выполняет поиск требуемой записи. [13]
Для повышения эффективности повседневной работы очень важны организованность и порядок. При обработке данных обычно также используются различные методы их упорядочения в памяти. Однако оказывается, что эффективность поиска можно повысить, если вместо различных упорядоченных структур использовать так называемые беспорядочные или перемешанные структуры данных. Для работы с такими структурами и предназначены методы хеширования. [14]
В предисловии отмечалось, что вопросы представления данных в памяти ЭВМ тесно связаны с операциями, при помощи которых они обрабатываются. К числу таких операций относятся выборка, изменение, включение и исключение данных. В основе всех перечисленных операций лежит операция доступа, которую и нельзя рассматривать независимо от способа представления. К каким же данным, находящимся в памяти, необходимо иметь доступ. Безусловно, любое данное в памяти должно быть доступно. Однако в задачах поиска предполагается, что все данные хранятся в памяти с определенной идентификацией и, говоря о доступе, имеют в виду прежде всего доступ к данным ( называемым ключами), однозначно идентифицирующим связанные с ними совокупности данных. В свою очередь даже ключи не обязательно должны быть непосредственно доступными. В этой главе обсуждаются два класса методов, реализующих доступ к данным по ключу: методы поиска по дереву и методы хеширования. [15]
Страницы: 1