Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

C++. Энциклопедия пользователя - Либерти Дж.

Либерти Дж. C++. Энциклопедия пользователя — Москва, 2001. — 581 c.
Скачать (прямая ссылка): enciklopediyapolzovatelya2001.djvu
Предыдущая << 1 .. 163 164 165 166 167 168 < 169 > 170 171 172 173 174 175 .. 280 >> Следующая

S (alpha) = 1/2 + 1/2 (1/(1-alpha)) ,
U (alpha) = 1/2 + 1/2 (1/(1-alpha))2
352
Хеширование и синтаксический анализ
Глава 14
353
В этой последовательности alpha — это коэффициент загрузки.
Эти формулы оценивают среднее количество попыток для успешного и неуспешного поиска. Эти формулы сформулированы Дональдом Кнутом (Donald Knuth) и подробно описаны в его книге The Art of Computer Programming.
По мере заполнения таблицы оба типа поиска — А(alpha) и U(alpha) — требуют все больше и больше времени. Когда таблица почти заполнена, количество проб достигает O(TR). Поиск, выполняемый при хешировании, зависит от коэффициента загрузки и не обязательно от количества элементов.
Квадратичное тестирование
Проблема производительности при линейном тестировании вызвана образованием групп в результате использования линейной тестовой последовательности. При квадратичном тестировании используется другая последовательность, позволяющая избежать группировки. Эта последовательность представляется с помощью следующих равенств:
р0 = hash (key)
Pi = (P„+ia> m°d TR
В этой последовательности p. — это i-я проверка, a TR — количество элементов в таблице. Квадратичное тестирование переходит через большее количество ячеек по сравнению с линейным тестированием и, следовательно, приводит к меньшему группированию. Однако для всех ключей, которые отображаются в одну и ту же ячейку, используется одна и та же тестовая последовательность. Это приводит к ситуации, которая называется вторичным группированием. Самый большой недостаток квадратичного тестирования состоит в том, что, после того как просмотрена примерно половина ячеек, последовательность начинает повторяться. В результате пустые ячейки пропускаются. Для улучшения ситуации можно использовать разновидность квадратичного тестирования:
р„ = hash (key)
Pi = <P0+i2> mod TR
Однородное тестирование — это теоретическая тестовая последовательность, которая, по существу, является случайной и в которой каждая ячейка может быть выбрана с одинаковой вероятностью. При таком тестировании не возникает ни первичного, ни вторичного группирования. Среднее количество проб для такой последовательности можно выразить с помощью следующих равенств:
S (alpha) = 1/а1рЬа*1я (1/ (1-alpha))
U(alpha) = 1/(1-alpha)
Здесь alpha — это коэффициент загрузки.
В результате будет получено приблизительное число попыток для успешного и неуспешного поиска. Эти формулы написаны Дональдом Кнутом (Donald Knuth) и подробно рассмотрены в его книге The Art of Computer Programming.
На практике не существует методов генерации такой последовательности. Однако очень похожих результатов можно достичь с помощью метода двойного хеширования.
Тестирование двойного хеширования
При двойном хешировании используются две функции хеширования. Первая функция применяется к ключу. В случае возникновения конфликта к результату первой функции применяется вторая функция и ее результат используется как смещение для нахождения новой ячейки. При этом используются следующие равенства:
р0 = hashl (key) offset = hash2(key)
Pi = (Pi.j + c) mod TR
Здесь TR — это количество ячеек.
Для гарантии проверки всей таблицы числа с и TR должны быть взаимно простыми.
Очень важно обеспечить, чтобы функции hashl и hash2 не зависели друг от друга. Если hashl приводит к конфликту, то hash2 не должна приводить к другому конфликту.
В свой книге Mathematics for the Analysis of Algorithms Дональд Кнут предлагает функции, помогающие избежать конфликтов:
12 Зак. 53
Обработка данных Часть III hashl (key) = key mod TR
hash2 (key) = key mod (TR-2)
Генерирование случайных чисел можно увеличить еще больше, если выбрать такое значение TR, чтобы TR и TR-x были простыми числами.
Пример. Применим метод двойного хеширования для набора телефонных номеров, который использовался в предыдущем примере:
8881234, 8882345, 8883456, 8884321, 8886543 Мы будем вставлять ключи в таблицу размером 11 и использовать следующие функции хеширования: hashl (key) = key mod 11
hash2 (key) = key mod 7
При использовании этого метода выполняются следующие шаги:
1. hashl (8881234) = 8881234 mod 11 = 10
2. hashl (8882345) = 8882345 mod 11 = 10 (конфликт)
Этот конфликт разрешается с помощью следующей последовательности: hash2(8882345) = 8882345 mod 7=3
3. hashl (8883456) = 8883456 mod 11 = 10 (конфликт)
Этот конфликт разрешается с помощью следующей последовательности: hash2(8883456) = 8883456 mod 7=1
4. hashl (8884321) = 8884321 mod 11 = 6
5. hashl (8885432) = 8885432 mod 11 = 6 (конфликт)
Этот конфликт разрешается с помощью следующей последовательности: hash2(8885432) = 8885432 mod 7=3 (конфликт)
Теперь можно использовать линейное тестирование; следующая пустая ячейка — 4.
6. hashl (8886543) = 8886543 mod 11 = 6 (конфликт)
Этот конфликт разрешается с помощью следующей последовательности: hash2(8886543) = 8886543 mod 7=1 (конфликт)
Используя линейное тестирование, получим следующую пустую ячейку с индексом 2.
В результате телефонные номера будут вставлены в таблицу следующим образом:
Предыдущая << 1 .. 163 164 165 166 167 168 < 169 > 170 171 172 173 174 175 .. 280 >> Следующая