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