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

Переполнение таблицы и рехеширование

Читайте также:
  1. III. Статистические таблицы
  2. Активный запрос на создание таблицы
  3. Анализ таблицы сложения. Ознакомление дошкольников с арифметическими действиями и вычислительными приемами.
  4. Безработица является неотъемлемой чертой общества с рыночной экономикой, что наглядно видно по данным таблицы 3.1.
  5. Булева алгебра. Таблицы истинности. Основные законы.
  6. Бум и всеобщее переполнение рынка
  7. Ввод данных в таблицы. Редактирование записей данных
  8. Вычисляемые таблицы.
  9. ГЛАВА IV. СТАТИСТИЧЕСКИЕ ТАБЛИЦЫ.
  10. Дан фрагмент таблицы
  11. Дан фрагмент таблицы.
  12. Дан фрагмент электронной таблицы. Для этого фрагмента таблицы истинно утверждение, что в ячейку...

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

Рис.3.5. Циклический переход к началу таблицы.

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

Рассмотрим данный способ на примере метода линейного опробования. При вычислении адреса очередного элемента можно ограничить адрес, взяв в качестве такового остаток от целочисленного деления адреса на длину таблицы n.

Вставка

· i = 0

· a = (h(key) + c*i) mod n

· Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

· i = i + 1, перейти к шагу 2

В данном алгоритме мы не учитываем возможность многократного превышения адресного пространства. Более корректным будет алгоритм, использующий сдвиг адреса на 1 элемент в случае каждого повторного превышения адресного пространства. Это повышает вероятность найти свободные элементы в случае повторных циклических переходов к началу таблицы.

Вставка

· i = 0

· a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

· Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

· i = i + 1, перейти к шагу 2

· a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

Рассматривая возможность выхода за пределы адресного пространства таблицы, мы не учитывали факторы заполненности таблицы и удачного выбора хеш-функции. При большой заполненности таблицы возникают частые коллизии и циклические переходы в начало таблицы. При неудачном выборе хеш-функции происходят аналогичные явления. В наихудшем варианте при полном заполнении таблицы алгоритмы циклического поиска свободного места приведут к зацикливанию. Поэтому при использовании хеш-таблиц необходимо стараться избегать очень плотного заполнения таблиц. Обычно длину таблицы выбирают из расчета двукратного превышения предполагаемого максимального числа записей. Не всегда при организации хеширования можно правильно оценить требуемую длину таблицы, поэтому в случае большой заполненности таблицы может понадобиться рехеширование. В этом случае увеличивают длину таблицы, изменяют хеш-функцию и переупорядочивают данные.

Производить отдельную оценку плотности заполнения таблицы после каждой операции вставки нецелесообразно, поэтому можно производить такую оценку косвенным образом √ по числу коллизий во время одной вставки. Достаточно определить некоторый порог числа коллизий, при превышении которого следует произвести рехеширование. Кроме того, такая проверка гарантирует невозможность зацикливания алгоритма в случае повторного просмотра элементов таблицы.

Рассмотрим алгоритм вставки, реализующий предлагаемый подход.

Вставка

· i = 0

· a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

· Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

· Если i > m, то стоп требуется рехеширование

· i = i + 1, перейти к шагу 2

В данном алгоритме номер итерации сравнивается с пороговым числом m. Следует заметить, что алгоритмы вставки, поиска и удаления должны использовать идентичное образование адреса очередной записи.

Удаление

· i = 0

· a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

· Если t(a) = key, то t(a) =удалено, стоп элемент удален

· Если t(a) = свободно или i>m, то стоп элемент не найден

· i = i + 1, перейти к шагу 2

Поиск

· i = 0

· a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n

· Если t(a) = key, то стоп элемент найден

· Если t(a) = свободно или i>m, то стоп элемент не найден

· i = i + 1, перейти к шагу 2


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)