Метод функции середины квадрата

Метод функции середины квадрата

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

Способ свертки

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

В качестве хеш-функции также используют функцию Метод функции середины квадрата преобразования системы счисления. Ключ, записанный как число в некой системе счисления P, интерпретируется как число в системе счисления Q>P. Обычно выбирают Q=P+1. Это число переводится из системы Q назад в систему P, приводится к размеру места записей и интерпретируется как адресок.

Открытое хеширование

Основная мысль Метод функции середины квадрата базисной структуры при открытом (наружном) хешировании состоит в том, что возможное огромное количество (может быть, нескончаемое) разбивается на конечное число классов. Для В классов, пронумерованных от 0 до В-1, строится хеш-функция h(x) такая, что для хоть какого элемента х начального огромного количества функция h(x) воспринимает целочисленное значение Метод функции середины квадрата из интервала 0,1,...,В-1, соответственное классу, которому принадлежит элемент х. Нередко классы именуют секторами, потому будем гласить, что элемент х принадлежит сектору h(x). Массив, именуемый таблицей частей и проиндексированный номерами частей 0,1,...,В-1, содержит заглавия для B списков. Элемент х, относящийся к i -му списку – это элемент начального огромного количества Метод функции середины квадрата, для которого h(x)=i.

Если сегменты приблизительно схожи по размеру, то в данном случае списки всех частей должны быть более маленькими при данном числе частей. Если начальное огромное количество состоит из N частей, тогда средняя длина списков будет N/B частей. Если можно оценить величину N и избрать В как Метод функции середины квадрата можно поближе к данной величине, то в каждом перечне будет один либо два элемента. Тогда время выполнения операторов словарей будет малой неизменной величиной, не зависящей от N.

Закрытое хеширование

При закрытом (внутреннем) хешировании в хеш-таблице хранятся конкретно сами элементы, а не заглавия списков частей. Потому в каждой записи (секторе) может Метод функции середины квадрата храниться только один элемент. При закрытом хешировании применяется методика повторного хеширования. Если осуществляется попытка поместить элемент х в сектор с номером h(х), который уже занят другим элементом (коллизия), то в согласовании с методикой повторного хеширования выбирается последовательность других номеров частей h1(х),h2(х),..., куда можно поместить Метод функции середины квадрата элемент х. Каждое из этих местоположений поочередно проверяется, пока не будет найдено свободное. Если свободных частей нет, то, как следует, таблица заполнена, и элемент х добавить нельзя.

При поиске элемента х нужно просмотреть все местоположения h(x), h1(х), h2(х), ..., пока не будет найден х либо пока Метод функции середины квадрата не повстречается пустой сектор. Чтоб разъяснить, почему можно приостановить поиск при достижении пустого сектора, представим, что в хеш-таблице не допускается удаление частей. Пусть h3(х) – 1-ый пустой сектор. В таковой ситуации нереально нахождение элемента х в секторах h4(х),h5(х) и дальше, потому что при вставке Метод функции середины квадрата элемент х вставляется в 1-ый пустой сектор, как следует, он находится кое-где до сектора h3(х). Но если в хеш-таблице допускается удаление частей, то при достижении пустого сектора, не обнаружив элемента х, нельзя быть уверенным в том, что его вообщем нет в таблице, потому что сектор может стать пустым уже Метод функции середины квадрата после вставки элемента х. Потому, чтоб прирастить эффективность данной реализации, нужно в сектор, который освободился после операции удаления элемента, поместить специальную константу, которую назовем, к примеру,DEL. В качестве кандидатуры специальной константе можно использовать дополнительное поле таблицы, которое указывает состояние элемента. Принципиально различать константы DEL и Метод функции середины квадрата NULL – последняя находится в секторах, которые никогда не содержали частей. При таком подходе выполнение поиска элемента не просит просмотра всей хеш-таблицы. Не считая того, при вставке частей сегменты, помеченные константой DEL, можно трактовать как свободные, таким макаром, место, освобожденное после удаления частей, можно в какой-то момент использовать повторно Метод функции середины квадрата. Но если нереально конкретно сходу после удаления частей пометить освободившиеся сегменты, то следует предпочесть закрытому хешированию схему открытого хеширования.

Существует несколько способов повторного хеширования, другими словами определения местоположений h(x),h1(х),h2(х),...:

· линейное опробование;

· квадратичное опробование;

· двойное хеширование.

Линейное опробование сводится к поочередному перебору частей таблицы с неким Метод функции середины квадрата фиксированным шагом:

адресок=h(x)+ci,

где i – номер пробы разрешить коллизию;

c – константа, определяющая шаг перебора.

При шаге, равном единице, происходит поочередный перебор всех частей после текущего. Квадратичное опробованиеотличается от линейного тем, что шаг перебора частей нелинейно находится в зависимости от номера пробы отыскать свободный сектор Метод функции середины квадрата:

адресок=h(x)+ci+di2,

где i – номер пробы разрешить коллизию,

c и d – константы.

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

Еще одна Метод функции середины квадрата разновидность способа открытой адресации, которая именуется двойным хешированием, базирована на нелинейной адресации, достигаемой за счет суммирования значений основной и дополнительной хеш-функций:

адресок=h(x)+ih2(x).

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

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

В случае внедрения схемы закрытого Метод функции середины квадрата хеширования скорость выполнения вставки и других операций зависит не только лишь от равномерности рассредотачивания частей по секторам хеш-функцией, да и от избранной методики повторного хеширования(опробования) для разрешения коллизий, связанных с попытками вставки частей в уже заполненные сегменты. К примеру, методика линейного опробования для разрешения коллизий – не Метод функции середины квадрата самый наилучший выбор.

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

Задание

1. Сделать динамический массив из записей (в согласовании с вариантом), содержащий более 100 частей. Для наполнения частей массива использовать ДСЧ.

2. Предугадать сохранение массива в файл и загрузку Метод функции середины квадрата массива из файла.

3. Предугадать возможность прибавления и удаления частей из массива (файла).

4. Выполнить поиск элемента в массиве по ключу в согласовании с вариантом. Для поиска использовать хэш-таблицу.

5. Подсчитать количество коллизий при размере хэш-таблицы 40, 75 и 90 частей.

Вариант Данные Ключ (string) Хэш-функция Способ рехеширования
ФИО, группа Метод функции середины квадрата, рейтинг ФИО H(k)=k mod M Способ цепочек
ФИО, №счета, сумма №счета H(k)= [M (kAmod1)], 0 Способ открытой адресации
ФИО, №счета, сумма ФИО H(k)=k mod M Способ открытой адресации
ФИО, №паспорта, адресок №паспорта H(k)= [M (kAmod1)], 0 Способ цепочек
ФИО, №паспорта, адресок ФИО H(k)=k mod M Способ цепочек
ФИО, №паспорта, адресок Адресок H(k)= [M (kAmod1)], 0 Способ открытой адресации
ФИО, №телефона, адресок №телефона H(k)=k mod M Способ открытой адресации
ФИО, №телефона Метод функции середины квадрата, адресок ФИО H(k)= [M (kAmod1)], 0 Способ цепочек
ФИО, №телефона, адресок Адресок H(k)=k mod M Способ цепочек
ФИО, №паспорта, №телефона №телефона H(k)= [M (kAmod1)], 0 Способ открытой адресации
ФИО, №паспорта, №телефона №паспорта H Метод функции середины квадрата(k)=k mod M Способ открытой адресации
ФИО, №паспорта, №телефона ФИО H(k)= [M (kAmod1)], 0 Способ цепочек
ФИО, дата_рождения, адресок дата_рождения H(k)=k mod M Способ цепочек
ФИО, дата_рождения, адресок адресок H(k)= [M (kAmod1)], 0 Способ открытой адресации
ФИО, дата_рождения, адресок ФИО H(k)=k mod M Способ открытой адресации
ФИО, дата_рождения, №телефона дата_рождения H(k)= [M (kAmod1)], 0 Способ цепочек
ФИО, дата_рождения, №телефона ФИО H(k)=k Метод функции середины квадрата mod M Способ цепочек
ФИО, дата_рождения, №телефона №телефона H(k)= [M (kAmod1)], 0 Способ открытой адресации
ФИО, дата_рождения, №паспорта, №паспорта, H(k)=k mod M Способ открытой адресации
ФИО, дата_рождения, №паспорта, дата_рождения, H(k)= [M (kAmod1)], 0 Способ цепочек

Методические указания

1. Для выбора действий использовать меню.

2. Для прибавления частей в файл использовать вспомогательную структуру для хранения частей в оперативки (перечень). Добавление должно осуществляться в начало, в конец файла и на позицию с данным номером.

3. Удаление должно осуществляться по главному полю и по номеру. Удаляемые из Метод функции середины квадрата файла записи помечаются как удаленные, когда их количество превзойдет половину файла, их можно удалять. При удалении использовать вспомогательную структуру для хранения частей в оперативки (перечень).

4. Предугадать возможность отмены последней операции удаления.

5. Корректировка производится по ключу и по номеру.

6. Предугадать команду «Сохранить изменения», по которой модифицированные данные из перечня Метод функции середины квадрата переписываются в файл.

Содержание отчета

1. Постановка задачки (общая и для определенного варианта).

2. Анализ задачки.

3. Проектирование функций для реализации намеченных целей (заглавие функции, предназначение, входные характеристики, итог).

4. Испытания для каждой функции.

5. Тест для всеохватывающей задачки (интеграция).

6. Листинг программки.


metod-3-nachinaya-s-konca.html
metod-5-metod-dolevogo-uchastiya-v-rinke.html
metod-6-upravlencheskie-rashodi-upravlencheskie-rashodi-po-okonchanii-mesyaca-spisivayutsya-napryamuyu-na-sebestoimost-prodazh.html