Инструменты пользователя

Инструменты сайта


examination:bd:question42

Вопрос №42. Хэш-функции.

8.3 Статические хеш-функции Недостаток индексных схем состоит в том, что для обнаружения записей приходится обращаться к индексам. Использование хеширования в качестве способа адресации избавляет от необходимости поддерживать и просматривать индексы. Отказ от индексов устраняет необходимость при поиске записи дважды обращаться к вспомогательному запоминающему устройству: один раз для чтения индекса и второй – для доступа к записи. Основной принцип состоит в том, чтобы заменить количество времени и операций, необходимое для записи, поддержания и просмотра индексов, на время, которое требуется центральному процессору на выполнение алгоритма хеширования, генерирующего адрес записи. Алгоритм хеширования – это процедура вычисления адреса записи на основании некоторого поля записи, обычно ключа.

8.4 Динамические хеш-функции По мере роста БД число конфликтов при использовании статических хеш-функций растёт. Это приводит к задержкам доступы а к данным. Одна из стратегий решения этой проблемы состоит в оценке нужного в будущем объёма памяти и его резервировании, но при этом неэффективно используется память. Другой приём заключается в захвате дополнительного объёма памяти по мере роста файла в сочетании с реорганизацией файла. Это также приводит к задержкам, связанным а пересчётом хеш-функции для каждой записи файла и новым распределением адресов. Более удачным подходом является использование динамических хеш-функций. Для примера возьмём метод, называемый растяжимым хешированием, который разбивает или сливает вместе блоки по мере роста или сокращении БД. Это гарантирует эффективное использование памяти.

examination/bd/question42.txt · Последние изменения: 2014/01/15 08:12 (внешнее изменение)