Методы программирования. Громов Ю.Ю - 120 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

120
чем то, что у всех дни рождения окажутся различными. Иными словами,
если выбрать случайную функцию, отображающую 23 ключа в таблицу
размером 365, вероятность того, что никакие два ключа не будут отобра-
жены в одно и то же место таблицы, составляет 0.4927, т.е. менее поло-
вины.
Событие, заключающееся в том, что для двух различных ключей K
i
и K
j
имеет место одинаковое значение хеш-функции: h(K
i
) = h(K
j
), назы-
вается коллизией. Поэтому для использования хеширования программист
должен решить две практически независимые задачи – выбрать хеш-
функцию и способ разрешения коллизий.
Далее предполагается, что хеш-функция имеет не более М различ-
ных значений, причём для любого ключа K справедливо соотношение
0 ≤ h(K) < М. (58)
Многочисленные тесты показали хорошую работу хеш-функции,
представляющей собой остаток от деления на М:
h(K) = K mod M. (59)
Самым очевидным путём решения проблемы возникающих колли-
зий является поддержка М связных списков, по одному для каждого воз-
можного значения хеш-кода. При этом следует иметь М головных узлов
списков, пронумерованных, например, от 1 до М, а каждый узел связан-
ного списка должен иметь поле LINK для размещения связи со следую-
щим узлом. После хеширования ключа просто выполняется последова-
тельный поиск в списке с номером h(K) + 1.
На рисунке 44 представлена простая схема с цепочками при М = 9
для последовательности из ключей K = 830, 585, 516, 432, 571, 161 и 433,
имеющих хеш-коды h(K) + 1 = 3, 1, 4, 1, 5, 9 и 2 соответственно. В первом
списке содержится два элемента, три списка пусты.
В общем случае, если имеется N ключей и М списков, средний раз-
мер списка будет равен N/М, следовательно, хеширование приводит к
уменьшению среднего количества работы, необходимой для последова-
тельного поиска, примерно в М раз.
Для повышения быстродействия желательны большие значения М,
однако в этом случае слишком многие списки будут пусты и будут зря
расходовать память на N записей и М + N ссылок. Иногда можно совер-
шать проход по всем данным для поиска заголовков списков, которые
будут использоваться, а затем при втором проходе вставлять «перепол-
няющие» записи в пустые места. Однако зачастую это непрактично или
невозможно, поэтому хотелось бы иметь метод, работающий с каждой
записью только раз при помещении её в систему. Следующий алгоритм
позволяет быстро решить эту задачу.

Страницы