Методы разрешения коллизий

Коллизии.

Назначение и принципы организации таблиц идентификаторов

III. Структуры, организация, хранение и поиск данных

Інтеграл з перемінною верхньою межею

Визначення 3. Нехай функція інтегрована за Риманом на сегменті. Інтегралом з перемінною верхньою границею від функції називається функція

.

Приклад. Нехай на сегменті розглядається функція. Оскільки неперервна на сегменті, вона інтегрована за Риманом на цьому сегменті, а також на будь-якому сегменті. Тоді за попереднім визначенням для функції можна визначити інтеграл з перемінною верхньою границею:

.

Визначений інтеграл з перемінною верхньою границею є функцією, його значення можна обчислити в будь-якій точці сегменту. Для того, щоб обчислити треба в інтеграл замість верхньої змінної границі поставити конкретне значення і обчислити звичайний інтеграл Римана. Наприклад:

Теорема. Нехай функція інтегрована за Риманом на сегменті, тоді функція неперервна в кожній точці.

Доказ. Візьмемо будь які аргументи і розглянемо.

Нехай спочатку:

Оскільки інтегрована за Риманом на сегменті, то вона обмежена на цьому сегменті, тобто

, що для,

тоді

. (21)

Розглянемо тепер випадок, коли. Аналогічно отримаємо, що тут має місце нерівність

. (22)

Об’єднуючи (21) і (22), отримаємо, що для

. (23)

Враховуючи (23), маємо:

, що таких, що виконується:

що означає рівномірну неперервність (за визначенням рівномірної неперервності), а тому і просто неперервність в кожній точці.

Теорема. Нехай функція інтегрована за Риманом на сегменті і неперервна в точці, тоді диференційована в точці і

.

Зауваження. Умова неперервності функції в точці не є необхідною для диференційованості функції в точці.

Приклад. Нехай на за виключенням скінченної кількості точок, де. Тоді

для,

тому диференційована в кожній точці, хоча має усувні розриви в скінченній кількості точок.

Зауваження. Якщо має в точці розрив І-го роду, то недиференційована в точці (теорема Дарбу).

4. Рехеширование (продолжение).

Алгоритм поиска элемента в таблице идентификаторов

· Вычислить значение хеш-функции n = h(A) для искомого элемента A.

· Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе – сравнить имя элемента в ячейке n с именем искомого элемента A: если они совпадают, то элемент найден и алгоритм завершен, иначе – i:=1 и перейти к шагу 3.

· Вычислить n_i = h_i(A). Если ячейка по адресу n_i пустая или n = n_i, то элемент не найден, и алгоритм завершен, иначе – сравнить имя элемента в ячейке n_i с именем искомого элемента A: если они совпадают, то элемент найден и алгоритм завершен, иначе – i:=i+1 и повторить шаг 3.

Алгоритмы размещения и поиска элемента схожи по выполняемым операциям, поэтому они имеют одинаковые оценки времени, необходимого для их выполнения.

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

Для организации таблицы идентификаторов по методу рехеширования необходимо определить все хеш-функции h_i для всех i; функции h_i определяют как некоторые модификации хеш-функции h. Простым методом вычисления функции h_i(A) является ее организация в виде

h_i(A) = (h(A) + p_i) mod N_m

где p_i – некоторое вычисляемое целое число, N_m – максимальное значение из области значений хеш-функции h. При p_i = i h_i(A) = (h(A)+i) mod N_m

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

Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехеширования, например, использовать в качестве p_i для функции h_i(A)=(h(A)+p_i) mod N_m последовательности псевдослучайных целых чисел p₁, p₂, …, p_k. При хорошем выборе генератора псевдослучайных чисел длина последовательности k будет k=N_m.

Существуют также другие методы организации функций рехеширования h_i(A), основанные на квадратичных вычислениях или, например, на вычислении по формуле:

h_i(A) = (h(A)*i) mod N_m

если N_m – простое число.

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

Дата добавления: 2014-01-11