Хеширование

При ассоциативном доступе к хранимым записям, предполагающем определение местоположения записи по значениям содержащихся в ней данных, используются различные методы отображения значения ключа в адрес, например, методы хеширования (перемешивания).Принцип хеширования - для ускорения поиска информации область хранения данных разбивается на участки, каждому из которых ставится в соответствие некоторое значение (номер участка). Для определения, в какой участок будет помещена вновь добавляемая запись, к значению ключевого поля этой записи применяется так называемая хеш-функция h(K). Она преобразует значение ключа K в номер произвольного участка памяти (это свёртка ключа). При поиске записи по известному значению ключа K хеш-функция выдаёт номер, указывающий на участок памяти, в котором надо искать эту запись.Хеш-функция h(K) должна выдавать такие значения номеров участков памяти, чтобы обеспечить равномерное распределение записей в памяти. Недостаток методов подбора хеш-функций - количество данных и распределение значений ключа должны быть известны заранее; записи неупорядочены по значению ключа, что приводит к дополнительным затратам. Преимущества: обращение к данным происходит за одну операцию ввода/вывода, т.к. значение ключа непосредственно преобразуется в адрес соответствующей записи. Рассмотр.2 основных типов хеш-функций: Один из них основан на делении, другой – на умножении. Метод деления использует остаток от деления на М:h(K)= К mod M.

Если М – чётное число, то при чётных К значение h(K) будет чётным, и наоборот, что даёт значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Мультипликативный метод -умножение значения ключа К на простую дробь и выделении правых значащих цифр результата: h(K)= М(((A/w)*К)mod 1), где w – размер машинного слова (обычно, 2³¹), А – целое число простое по отношению к w, а M – некоторая степень основания системы счисления ЭВМ (2^m). При использовании любых методов хеширования для размещения записей должен быть выделен участок памяти размером N. Для того чтобы полученное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так:

А(К) = h(K) mod N. Случай, когда для двух и более ключей выдаётся одинаковый номер участка, называется коллизией. Наличие коллизий снижает эффективность хеширования.Разрешение коллизий достигается путём рехеширования – специального алгоритма, который используется при размещении новой записи или при поиске существующей. В системах баз данных рехеширование выполняется одним из следующих способов:

1. Открытая адресация: новая запись размещается вслед за последней записью на данной странице или на следующей, если страница заполнена. Поиск записи осуществляется также последовательно.2.Использование коллизионных страниц: новая запись размещается на одной из коллизионных страниц, относящихся к таблице (в области переполнения). Нулевое значение такой ссылки говорит об отсутствии коллизий для данных, размещённых на этой странице.3. Многократное хеширование- при возникновении коллизии для поиска другого адреса применяется другая функция хеширования.

Билет № 4.

1 .Понятия, характеризующие функционирование и развитие системы. Классификации систем.

Понятия, характеризующие функционирование и развитие сис­темы.

Состояние-характеризуют мгно­венную фотографию, «срез» системы (система=S), остановку в ее развитии. Его определяют либо через входные воздействия и выходные сигналы (резуль­таты), либо через макропараметры, макросвойства S (давление, скорость, ускорение). Равновесие-способность S в отсутствие внешних возмущающих воздействий (или при постоянных воздействиях) сохранять свое состояние сколь угодно долго. Устойчивость - способность S возвращаться в состояние равновесия после того, как она была из этого состояния выведена под влиянием внешних (или в S с ак­тивными элементами - внутренних) возмущающих воздействий. Состояние равновесия, в которое S способна возвращаться, называют устойчивым состоянием равновесия. Возврат в это состояние может сопровождаться колебательным процессом. Соответственно в сложных S возможны неустойчивые состояния равновесия. Развитие. Это понятие помогает объяснить сложные термодина­мические и информационные процессы в природе и обществе. Иссле­дование процесса развития, соотношения развития и устойчивости, изучение механизмов, лежащих в их основе, - наиболее сложные задачи теории S. Наиболее важные классификации S:Открытые и закрытые S. Понятие открытой S ввел Л. фон Берталакфи. Отличительные черты - способность обмениваться со средой массой, энергией и информацией. В отличие от них закрытые или замкнутые S предполагаются (разумеется, с точностью до принятой чувствительности модели) полностью лишенными этой способности, т. е. изолированны­ми от среды. Целенаправленные, целеустремленные S.В этом классе, в свою очередь, можно выделить S, в которых цели задаются извне (обычно это имеет место в закрытых системах), и S, в которых цели формируются внутри S (что характерно для откры­тых, самоорганизующихся S).Классификации S по сложности.Н.П, Бусленко предложил в силу отсутствия четкого определения от­несения S к разряду больших связывать понятие большая S с тем, какую роль играют при изучении S комплексные общесистемные вопросы, что зависит от свойств S и классов решаемых задач. Понятие большой S связывали в большей мере с важными для таких S понятиями эмерджентности(наличие у какой-либо системы особых свойств, не присущих её подсистемам и блокам), открытости, активностью элементов, в результате чего такая S обладает как бы «свободой воли», нестабильным и непредсказуемым поведением и другими харак­теристиками развивающихся, самоорганизующихся S. Б.С.Флейшман за основу классификации принимает сложность поведе­ния S. Классификация S по степени организован­ности-разделение S на хорошо организованные и плохо организованные, или диффузные. К этим двум классам был добавлен еще класс развивающихся или самоорганизующихся у S.