Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Квадратичное зонирование в хеш-таблице
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
NoobSofia NoobSofia вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.12.2012
По умолчанию Квадратичное зондирование в хеш-таблице - 06.01.2013, 10:22

Здравствуйте. Не могу разобраться в схеме выбора шага в квадратичном зондировании при работе с хеш-таблицей с открытой адресацией.
Хеш-функция выглядит следующим образом:
cpp Код:
h'(k, j) = (h(k) + c1*j + c2*j*j)%m
h(k) -- функция мультипликативного хеширования, с1 и с2 -- некоторые коэффициенты, подбираемые таким образом, чтобы просмотреть все ячейки таблицы.
При каждой новой пробе шаг меняется на некоторую, в свою очередь тоже меняющуюся, величину. Возможно, что при некоторых соотношениях h(k) и c1 c2 мы получим последовательность, которая будет бить в одни и те же ячейки таблицы (размер мой таблицы -- степень двойки). Как избегать таких ситуаций? Можно ли положить, что такое хеширование просто дает неудачный результат в некоторых случаях (при условии, что c1 и c2 обеспечивают теоретически верную трудоемкость), или следует обрабатывать такие ситуации, искусственно меняя шаг? Если следует, то как своевременно распознать такую ситуацию?

Последний раз редактировалось NoobSofia; 06.01.2013 в 10:47
Ответить с цитированием
Ads
Ответ

Метки
зондирование , коллизии , хеш-таблица , хеш-функция

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
кодировка в таблице simsalbim PHP 14 31.03.2007 11:10
Позиционирование в таблице StringGrid Droom Delphi 2 19.10.2006 18:54
Кодировка в таблице v0v41k C++ Builder 6 18.10.2006 18:38
Отображение изменений в таблице elf_grey C++ Builder 12 21.08.2006 12:28
Как сделать обновление в таблице Golik Delphi 2 04.05.2006 17:20
Одинаковые названия в таблице Хочу быть программистом C++ Builder 7 25.04.2006 23:04
Сложение строк в таблице Dimson C++ Builder 14 20.04.2006 21:26
Выборка данных в таблице SQL eva001 C++ Builder 12 09.04.2006 02:30
Слияние ячеек в таблице se7en Delphi 4 02.08.2005 08:37
Разделение строки в таблице blur Delphi 5 21.07.2005 15:06
Цветная ячейка в таблице Dimitrii Java 4 13.06.2004 17:08
кол-во записей в таблице Anonymous PHP 1 13.11.2003 11:16



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов