Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Эффективное представление множеств - часть 2


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

fct emptystore=store,

fct get=(store, key) data,

fct insert=(store, data) store,

fct delete=(store,key) store.

Способ действия этих функций можно представить следующими равенствами:

k = key(d) Þ get(insert(s, d), k) = d

k ¹ key(d) Þ get(insert(s, d), k) = get(s, k),

delete(emptystore, k) = emptystore,

k = key(d) Þ delete(insert(s, d), k) = delete(s, k),

k ¹ key(d) Þ delete(insert(s, d), k) = insert(delete(s, k), d).

Нижа будут представлены структуры данных для представления больших множеств данных, которые позволяют эффективно реализовывать указанные выше операции.

 

Метод хэширования

Метод хэширования

позволяет хранить множество элементов в линейном массиве длиной z. Для этого нужна функция расстановки («рассыпания»):

h: keyà[0:z-1],

которая каждый элемент типа key отображает на индекс в множестве [0:z-1]. Эта функция устанавливает, под каким индексом будет храниться данный элемент в массиве. Используем h(m) в качестве индекса (также называемого ключом) для запоминания элемента данных в массиве

sort store = [0:z-1] array data a.

Как правило, число элементов типа key значительно больше, чем z. Тогда функция h наверняка неинъективна. Возможно хранение элемента b с ключом m в массиве a под индексом h(m). Получаются следующие реализации функций:

fct emptystore = store: emptyarray,

fct get = (store

a, key k) data: a[h(k)]

fct insert = (store a, data d) store: update(a, h(key(d)), d),

fct delete = (store a, key k) store: update(a, h(k), empty).

Здесь предполагается, что empty обозначает элемент типа data, который играет роль держателя места. Функции работают корректно, пока для всех встречающихся ключей значения функции расстановки различны. Возникает проблема, когда нужно запоминать два различных элемента с ключами m1 и m2, и при этом оказывается h(m1)=h(m2).


- Начало -  - Назад -  - Вперед -