Хеширование

Cтраница 2

Изложение собственно хеширования на этом заканчивается. [16]

Второй метод хеширования предложен А. П. Ершовым [50] и называется открытой адресацией. Он предполагает наличие закольцованного массива для т записей и наличие понятия пустой записи. После этого для поступившего запроса х вычисляется значение хеш-функции h ( x), и если оно равно г, то просматривается с г-ой позиции массив записей пока запись х будет найдена или пока не встретится пустая запись. [17]

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

С методами хеширования связаны вместе с тем некоторые осложняющие обстоятельства. Прежде всего разные значения ключа могут давать одну и ту же свертку. Тогда при размещении не первой записи из множества записей с такими значениями ключей выделенное для записи пространство оказывается занятым другой записью. [19]

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

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

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

Второй метод хеширования предложен А. П. Ершовым [50] и называется открытой адресацией. Он предполагает наличие закольцованного массива для га записей и наличие понятия пустой записи. После этого для поступившего запроса х вычисляется значение хеш-функции / г ( ж), и если оно равно г, то просматривается с г-ой позиции массив записей пока запись х будет найдена или пока не встретится пустая запись. [23]

В методах хеширования, используемых для хранения множеств, в обоих способах обработки коллизий - рехешировании и последовательнрм сканировании - возникают трудности, если разрешены исключения Из множества. [24]

Квадратичная проверка. [25]

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

Рассмотрите схему раздельного хеширования для поиска по частичному соответствию из разд. Адреса участков содержат 12 бит. [27]

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

Поиск информации методом хеширования описан в § 4.4. Функция / преобразует слова словаря 5 в их адреса в памяти компьютера. Слова с одинаковыми адресами образуют список. [29]

Окно программы Chain. [30]

Страницы: 1 2 3 4