Реализация словарей

1. Сортированные или неотсортированные связанные списки;
2. Двоичные векторы (когда элементы множества можно сопоставить с элементами множества целых чисел 1,…., N для некоторого N;
3. использование массивов фиксированной длины с указателями на последнюю заполненную ячейку этого массива

 

 

Оператор	Способ реализации словаря
INSERT	O(N)	O(1)	O(N)
DELETE	O(N)	O(1)	O(N)
MEMBER	O(N)	O(1)	O(N)

 

Прямая адресацияприменяется, когда количество возможных значений невелико

Ключи – числа из множества U= {0, 1, …, m-1}

Для хранения множества используется массив T[0..m-1], называемый таблицей с прямой адресацией (direct-address table).