Реалізація множини

Розглянемо для простоти реалізацію звичайної, не навантаженої множини. (Реалізація навантаженої множини аналогічна реалізації звичайної, просто паралельно з елементами потрібно додатково зберігати навантаження елементів.) У звичайній реалізації множини її елементи зберігаються в масиві, починаючи з першої комірки. Спеціальна змінна містить поточне число елементів множини, тобто кількість використовуваних у цей момент комірок масиву.

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

У звичайній реалізації елементи множини зберігаються в масиві в довільному порядку. Це означає, що при пошуку елемента x доведеться послідовно перебрати всі елементи, поки ми або не знайдемо x, або не переконаємося, що його там немає. Нехай множина містить 1.00.00 елементів. Тоді, якщо x належить множині, доведеться переглянути в середньому 500.00 елементів, якщо немає - усі елементи. Тому звичайна реалізація підходить тільки для невеликих множин.