1. Множество — это структура данных, содержащая конечный набор элементов некоторого типа. Каждый элемент содержится только в одном экземпляре, т.е. разные элементы множества не равны между собой. Элементы множества никак не упорядочены. В множество M можно добавить элемент x, из множества M можно удалить элемент x. Если при добавлении элемента x он уже содержится в множестве M, то ничего не происходит. Аналогично, никакие действия не совершаются при удалении элемента x, когда он не содержится в множестве M. Наконец, для заданного элемента x можно определить, содержится ли он в множестве M. Множество — это потенциально неограниченная структура, оно может содержать любое конечное число элементов.

2. В некоторых языках программирования накладывают ограничения на тип элементов и на максимальное количество элементов множества. Так, иногда рассматривают множество элементов дискретного типа, число элементов которого не может превышать некоторой константы, задаваемой при создании множества. (Тип называется дискретным, если все возможные значения данного типа можно занумеровать целыми числами.) Для таких множеств употребляют название Bitset (``набор битов'') или просто Set. Как правило, для реализации таких множеств используется битовая реализация множества на базе массива целых чисел. Каждое целое число рассматривается в двоичном представлении как набор битов, содержащий 32 элемента. Биты внутри одного числа нумеруются справа налево (от младших разрядов к старшим); нумерация битов продолжается от одного числа к другому, когда мы перебираем элементы массива. К примеру, массив из десяти целых чисел содержит 320 битов, номера которых изменяются от 0 до 319. Множество в данной реализации может содержать любой набор целых чисел в диапазоне от 0 до 319. Число N содержится в множестве тогда и только тогда, когда бит с номером Nравен единице (программисты говорят бит установлен). Соответственно, если число N не содержится в множестве, то бит с номером N равен нулю (программисты говорят бит очищен). Пусть, например, множество содержит элементы 0, 1, 5, 34. Тогда в первом элементе массива установлены биты с номерами 0, 1, 5, во втором — бит с номером 2 = 34 - 32. Соответственно, двоичное представление первого элемента массива равно 10011 (биты нумеруются справа налево), второго — 100, это числа 19 и 4 в десятичном представлении. Все остальные элементы массива нулевые.

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

4. В программировании довольно часто рассматривают структуру чуть более сложную, чем просто множество: нагруженное множество. Пусть каждый элемент множества содержится в нем вместе с дополнительной информацией, которую называют нагрузкой элемента. При добавлении элемента в множество нужно также указывать нагрузку, которую он несет. В разных языках программирования и в различных стандартных библиотеках такие структуры называют Отображением (Map) или Словарем (Dictionary). Действительно, элементы множества как бы отображаются на нагрузку, которую они несут (заметим, что в математике понятие функции или отображения определяется строго как множество пар; первым элементом каждой пары является конкретное значение аргумента функции, вторым — значение, на которое функция отображает аргумент). В интерпретации Cловаря элемент множества — это иностранное слово, нагрузка элемента — это перевод слова на русский язык (разумеется, перевод может включать несколько вариантов, но здесь перевод рассматривается как единый текст).

5. Подчеркнем еще раз, что все элементы содержатся в нагруженном множестве в одном экземпляре, т.е. разные элементы множества не могут быть равны друг другу. В отличие от самих элементов, их нагрузки могут совпадать (так, различные иностранные слова могут иметь одинаковый перевод). Поэтому иногда элементы нагруженного множества называют ключами, их нагрузки — значениями ключей. Каждый ключ уникален. Принято говорить, что ключи отображаются на их значения.

6. В качестве примера нагруженного множества наряду со словарем можно рассмотреть множество банковских счетов. Банковский счет — это уникальный идентификатор, состоящий в случае российских банков из 20 десятичных цифр. Нагрузка счета — это вся информация, которая ему соответствует, включающая имя и адрес владельца счета, код валюты, сумму остатка, информацию о последних транзакциях и т.п.

7. Наиболее часто применяемая операция в нагруженном множестве — это определение нагрузки для заданного элемента x (значения ключа x ). Реализация этой операции включает поиск элемента x в множестве, поэтому эффективность любой реализации множества определяется прежде всего быстротой поиска.

8. Реализации множества: последовательный и бинарный поиск, хеширование

9. Рассмотрим для простоты реализацию обычного, не нагруженного, множества. (Реализация нагруженного множества аналогична реализации обычного, просто параллельно с элементами нужно дополнительно хранить нагрузки элементов.) В нативной реализации множества его элементы хранятся в массиве, начиная с первой ячейки. Специальная переменная содержит текущее число элементов множества, т.е. количество используемых в данный момент ячеек массива.

10. 

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

13. В наивной реализации элементы множества хранятся в массиве в произвольном порядке. Это означает, что при поиске элемента x придется последовательно перебрать все элементы, пока мы либо не найдем x, либо не убедимся, что его там нет. Пусть множество содержит 1,000,000 элементов. Тогда, если x содержится в множестве, придется просмотреть в среднем 500,000 элементов, если нет — все элементы. Поэтому наивная реализация годится только для небольших множеств.

14. Бинарный поиск

15. Пусть можно сравнивать элементы множества друг с другом, определяя, какой из них больше. (Например, для текстовых строк применяется лексикографическое сравнение: первые буквы сравниваются по алфавиту; если они равны, то сравниваются вторые буквы и т.д.) Тогда можно существенно убыстрить поиск, применяя алгоритм бинарного поиска. Для этого элементы множества хранятся в массиве в возрастающем порядке. Идея бинарного поиска иллюстрируется следующей шуточной задачей: : "Как поймать льва в пустыне? Надо разделить пустыню забором пополам, затем ту половину, в которой находится лев, снова разделить пополам и так далее, пока лев не окажется пойманным".

16. В алгоритме бинарного поиска мы на каждом шагу делим отрезок массива, в котором может находиться искомый элемент x, пополам. Рассматриваем элемент y в середине отрезка. Если x меньше y, то выбираем левую половину отрезка, если больше, то правую. Таким образом, на каждом шаге размер отрезка массива, в котором может находиться элемент x, уменьшается в два раза. Поиск заканчивается, когда размер отрезка массива (т.е. расстояние между его правым и левым концами) становится равным единице, т.е. через [log2n]+1 шагов, где n — размер массива. В нашем примере это произойдет после 20 шагов (т.к. log21000000 < 20 ). Таким образом, вместо миллиона операций сравнения при последовательном поиска нужно выполнить всего лишь 20 операций при бинарном.

17. Запишем алгоритм бинарного поиска на псевдокоде. Дан упорядоченный массив a вещественных чисел (вещественные числа используются для определенности; бинарный поиск можно применять, если на элементах множества определен линейный порядок, т.е. для любых двух элементов можно проверить их равенство или определить, какой их них больше). Пусть текущее число элементов равно n. Элементы массива упорядочены по возрастанию:

18. a[0] < a[1] < x xx < a[n - 1]

19. Мы ищем элемент x. Требуется определить, содержится ли x в массиве. Если элемент x содержится в массиве, то надо определить индекс i ячейки массива, содержащей x:

20. найти i: a[i] = x

21. Если же x не содержится в массиве, то надо определить индекс x, такой, что при добавлении элемента x в i -ю ячейку массива элементы массива останутся упорядоченными, т.е.

22. найти i: a[i-1] < x =< a[i]

23. (считается, что ). Объединив оба случая, получим неравенство

24. a[i-1] < x =< a[i]

25. Используем схему построения цикла с помощью инварианта. В процессе выполнения хранятся два индекса b и e (от слов begin и end), такие, что

26. a[b] < x =< a[e]

27. Индексы b и e ограничивают текущий отрезок массива, в котором осуществляется поиск. Приведенное неравенство является инвариантом цикла. Перед началом выполнения цикла рассматриваются разные исключительные случаи — когда массив пустой (n=0), когда x не превышает минимального элемента массива (x =< a[0]) и когда x больше максимального элемента (x > a[n-1]). В общем случае выполняется неравенство

28. a[0] < x =< a[n-1])

29. Полагая b = 0, e = n - 1, мы обеспечиваем выполнение инварианта цикла перед началом выполнения цикла. Условие завершения состоит в том, что длина участка массива, внутри которого может находится элемент x, равна единице:

30. b - e = 1

31. В этом случае

32. a[e-1] < x =< a[e]

33. т.е. искомый индекс i равен e, а элемент x содержится в массиве тогда и только тогда, когда x = a[e]. В цикле мы вычисляем середину c отрезка [b,e]

34. с = целая часть ((b+e)/2)

35. и выбираем ту из двух половин [b,c] или [c,e], которая содержит x. Для этого достаточно сравнить x со значением a[c] в середине отрезка. Завершение цикла обеспечивается тем, что величина e - b монотонно убывает после каждой итерации цикла.

36. Приведем текст алгоритма бинарного поиска:

37. лог алгоритм бинарный_поиск( вход: цел n, вещ a[n], вещ x, выход: цел i ) | Дано: n — число элементов в массиве a, | a[0] < a[1] < ... < a[n-1] | Надо: ответ := (x содержится в массиве), | вычислить i, такое, что | a[i-1] < x <= a[i] | (считая a[-1] = -беск., a[n] = +беск.) начало | цел b, e, c; | | // Рассматриваем сначала исключительные случаи | если (n == 0) | | то i = 0; | | ответ := ложь; | иначе если (x <= a[0]) | | i := 0; | | ответ := (x == a[0]); | иначе если (x > a[n-1]) | | i := n | | ответ := ложь; | иначе | | // Общий случай | | утверждение: a[0] < x <= a[n-1]; | | b := 0; e := n-1; | | | | цикл пока e - b > 1 | | | инвариант: a[b] < x и x <= a[e]; | | | c := целая часть((b + e) / 2); | | | если x <= a[c] | | | | то e := c; | | | иначе | | | | b := c; | | | конец если | | конец цикла | | | | утверждение: e - b == 1 и | | a[b] < x <= a[e]; | | i := e; | | ответ := (x == a[i]); | конец если конец алгоритма

Хеширование

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

Идея хеш-реализации состоит в том, что мы сводим работу с одним большим множеством к работе с массивом небольших множеств. Рассмотрим, к примеру, записную книжку. Она содержит список фамилий людей с их телефонами (телефоны — это нагрузка элементов множества). Страницы записной книжки помечены буквами алфавита; страница, помеченная некоторой буквой, содержит только фамилии, начинающиеся с этой буквы. Таким образом, все множество фамилий разбито на 28 подмножеств, соответствующих буквам латинского алфавита. При поиске фамилии мы сразу открываем записную книжку на странице, помеченной первой буквой фамилии, и в результате поиск значительно убыстряется.

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

Параметром реализации является число подмножеств, которое также называют размером хеш-таблицы. Пусть он равен N. Тогда хеш-функция должна принимать значения 0, 1, 2, ... , N - 1. Если изначально у нас есть некоторая функция H(x), принимающая произвольные целые неотрицательные значения, то в качестве хеш-функции можно использовать функциюh(x), равную остатку от деления H(x) на N.

Множество M разбивается на N непересекающихся подмножеств, занумерованных индексами от 0 до N - 1. Подмножество Miс индексом i содержит все элементы x из M, значения хеш-функции для которых равняются i:

При поиске элемента x сначала вычисляется значение его хеш-функции: t = h(x). Затем мы ищем x в подмножестве Mt . Поскольку это подмножество небольшое, то поиск осуществляется быстро. Для эффективной реализации каждое подмножество должно в большинстве случаев содержать не больше одного элемента. Следовательно, размер хеш-таблицы N должен быть больше, чем среднее число элементов множества. Обычно N выбирают превышающим число элементов множества примерно в три раза. В примере с записной книжкой это означает, что в ней должно быть записано около 10 фамилий. В таком случае большинство страниц либо пустые, либо содержат одну фамилию, хотя не исключены и коллизии, когда на одной странице записаны несколько фамилий.

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

Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).

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

Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.

Коллизией хеш-функции H называется два различных входных блока данных x и y таких, что H(x) = H(y).

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