7. ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА)

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

мМетод расстановок (хеширования) направлен на быстрое решение задачи о местоположении элемента в структуре данных. В методе расстановок данные организованы как обычный массив. Поэтому Н - отображение, преобразующее ключи в индексы массива, отсюда и появилось название«преобразование ключей», обычно даваемое этому методу. Следует заметить, что нет никакой нужды обращаться к каким-либо процедурам динамического размещения, ведь массив — это один из основных, статических объектов. Метод преобразования ключей часто используется для таких задач, где можно с успехом воспользоваться и деревьями.

Основная трудность, связанная с преобразованием ключей, заключается в том, что множество возможных значений значительно шире множества допустимых адресов памяти (индексов массива). Возьмем в качестве примера имена, включающие до 16 букв и представляющие собой ключи, идентифицирующие отдельные индивиды из множества в тысячу персон. Следовательно, мы имеем дело с 26¹⁶ возможными ключами, которые нужно отобразить в 10³ возмож­ных индексов. Поэтому функция Н будет функцией класса «много значений в одно значение». Если дан некоторый ключ k, то первый шаг операции поиска — вычисление связанного с ним индекса h = H(k), а второй (совершенно необходимый) — проверка, действительно ли h идентифицирует в массиве (таблице) Т элемент с ключом k.

7.1. Выбор функции преобразования

Само собой разумеется, что любая хорошая функция преобразования должна как можно равномернее распределять ключи по всему диапазону значений индекса. Если это требование удовлетворяется, то других ограничений уже нет, и даже хорошо, если преобразование будет выглядеть как совершенно слу­чайное. Такая особенность объясняет несколько ненаучное название этого метода — «перемалывание» (хеширование), т. е. дробление аргумента, превращение его в какое-то «месиво». Функция же Н будет называться «функцией расстановки». Ясно, что Н должно вычисляться достаточно эффективно, т. е. состоять из очень небольшого числа основных ариф­метических операций.

Представим себе, что есть функция преобразования ORD(k), обозначающая порядковый номер ключа k в множестве всех возможных ключей. Кроме того, будем считать, что индекс массива i лежит в диапазоне 0 ... N — 1, где N — размер массива. В этом случае ясно, что нужно выбрать следующую функцию:


H(k) = ORD(k) MOD N


Для нее характерно равномерное отображение зна­чений ключа на весь диапазон изменения индексов, поэтому ее кладут в основу большинства преобразо­ваний ключей. Кроме того, при N, равном степени двух, эта функция эффективно вычисляется. Об этом говорит сайт https://intellect.icu . Однако если ключ представляет собой последовательность букв, то именно от такой функции и следует отказаться. Дело в том, что в этом случае допущение о равновероятности всех ключей ошибочно. В резуль­тате слова, отличающиеся только несколькими сим­волами, с большой вероятностью будут отображаться в один и тот же индекс, что приведет к очень неравномерному распределению. Поэтому на практике ре­комендуется в качестве N брать простое число. Следствием такого выбора будет необходимость использования полной операции деления, которую уже нельзя заменить выделением нескольких двоичных цифр. 

7.2. Алгоритм

Если обнаруживается, что строка таблицы, соответствующая заданному ключу, не содержит желаемого элемента, то, значит, произошел конфликт, т. е. два элемента имеют такие ключи, которые отобра­жаются в один и тот же индекс. В этой ситуации нужна вторая попытка с индексом, вполне опреде­ленным образом получаемым из того же заданного ключа. Существует несколько методов формирования вторичного индекса. Очевидный прием — связывать вместе все строки с идентичным первичным индексом H(k). Превращая их в связанный список. Такой прием называется прямым связыванием (direct chaining). Элементы получающегося списка могут либо поме­щаться в основную таблицу, либо нет; в этом случае память, где они размещаются, обычно называется областью переполнения. Недостаток такого приема в том, что нужно следить за такими вторичными списками и в каждой строке отводить место для ссылки (или индекса) на соответствующий список конфликтующих элементов.

Другой прием разрешения конфликтов состоит в том, что мы совсем отказываемся от ссылок и вместо этого просматриваем другие строки той же таб­лицы — до тех пор, пока не обнаружим желаемый элемент или же пустую строку. В последнем случае мы считаем, что указанного ключа в таблице нет. Такой прием называется открытой адресацией. Естественно, что во второй попытке последователь­ность индексов должна быть всегда одной и той же для любого заданного ключа. В этом случае алгоритм просмотра строится по такой схеме:


h = H(k) 

i = 0

repeat 

if T(h) = k 

then элемент найден

else if T(h) = free 

then элемента в таблице нет

else {конфликт}

i := i + 1 

h := H(k) + G(i)

endif

endif

until либо найден, либо нет в таблице (либо она полна)


Предлагались самые разные функции G(i) для разрешения конфликтов. Приведенный в работе Морриса (1968) обзор стимулировал активную деятельность в этом направлении. Самый простой прием — посмотреть следующую строку таблицы (будем считать ее круговой), и так до тех пор, пока либо будет найден элемент с указанным клю­чом, либо встретится пустая строка. Следовательно, в этом случае G(i)==i, а индексы h_i, употребляемые при последующих попытках, таковы:


h₀ := H(k)

h_i := (h_i + i) MOD N, i = 1 … N - 1


Такой прием называется линейными пробами, его недостаток заключается в том, что строки имеют тенденцию группироваться вокруг первичных ключей (т. е. ключей, для которых при включении конфликта не возникало). Конечно, хотелось бы выбрать такую функцию G, которая вновь равномерно рассеивала бы ключи по оставшимся строкам. Однако на прак­тике это приводит к слишком большим затратам, потому предпочтительнее некоторые компромиссные методы; будучи достаточно простыми с точки зрения вычислений, они все же лучше линейной функции. Один из них — использование квадратичной функ­ции, в этом случае последовательность пробуемых индексов такова:


h₀ := H(k)

h_i := (h_i + i²) MOD N, i > 0


Если воспользоваться рекуррентными соотношениями для h_i = i² и d_i = 2i + l при h₀ = 0 и d₀ = l, то при вычислении очередного индекса можно обойтись без операции возведения в квадрат.


h_i+1 = h_i + d_i

d_i+1 = d_i + 2 (i > 0)


Такой прием называется квадратичными пробами, существенно, что он позволяет избежать группирова­ния, присущего линейным пробам, не приводя прак­тически к дополнительным вычислениям. Небольшой же его недостаток заключается в том, что при поиске пробуются не все строки таблицы, т. е. при включе­нии элемента может не найтись свободного места, хотя на самом деле оно есть. Если размер N — про­стое число, то при квадратичных пробах просматри­вается по крайней мере половина таблицы. Такое утверждение можно вывести из следующих рассуж­дений. Если i-я и j-я пробы приводят к одной и той же строке таблицы, то справедливо равенство


i² MOD N = j² MOD N


или


( i² – j² ) = 0 ( MOD N )


Разлагая разность на два множителя, получаем 


( i + j )( i - j ) = 0 ( MOD N )


Поскольку i  j, то либо i, либо j должны быть больше N/2, чтобы было справедливо равенство i + j = cN, где с — некоторое целое число. На практике упомянутый недостаток не столь существен, так как N/2 вторичных попыток при разрешении конфликтов встречаются очень редко, главным образом в тех случаях, когда таблица почти заполнена.


Контрольные вопросы

1. 
   Для чего предназначен метод расстановок ?
2. 
   От чего зависит положение элемента в массива в методе расстановок ?
3. 
   Какую функцию возможно использовать в качестве хэш-функции: 
4. 
   Что называется конфликтом ?
5. 
   Какой из методов является методом разрешения конфликтов.
6. 
   Какой из методов разрешения конфликтов позволяет более равномерно распределить элементы по массиву.
7. 
   Почему невозможно применять в качестве H(k) функцию Trunc(sqrt(k⁵- i*tan(k))) MOD N ?

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

Из статьи мы узнали кратко, но содержательно про преобразование ключей расстановка

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.