6.4. Методы открытой адресации
 

Используется только одна хеш-таблица с N элементами, цепочки переполнения не создаются. Суть метода заключается в том, чтобы после входа в таблицу по адресу а_i полностью отказаться от указателей и просто по некоторому правилу (алгоритму) просматривать строки таблицы, пока не будут найдены либо свободная строка при вставке нового элемента, либо ключ к при поиске элемента.

Алгоритм открытой адресации в общем виде можно описать следующим образом.

1. Вычисляем адрес точки входа в таблицу по ключу к а = f(k). Установим счетчик i = 0.
2. Если строка Т[а] свободна, то, значит, записи с ключом к в таблице нет. При вставке в строку помещаются запись и удачный конец алгоритма, при поиске конец алгоритма при отсутствии ключа.
3. Если ключ в строке Т[а] равен k, тогда при вставке — конец алгоритма по признаку «дублирующий ключ», при поиске — удачный конец и возврат адреса строки a_i.
4. В противном случае — коллизия. Увеличиваем счетчик на 1: i = (i+ 1) и по некоторой функции вычисляем адрес ячейки внутри таблицы а_i= g(f(k), i).

Функции g(f(k), i), 1≤ i ≤ N, определяют последовательность адресов для просмотра элементов таблицы. Их выбор вызывает некоторые трудности и в основном определяется особенностями использования таблицы при решении конкретной задачи. Наиболее распространенными схемами открытой адресации являются:

• линейная открытая адресация;
• квадратичная открытая адресация;
• открытая адресация с двойным хешированием.

Линейная открытая адресация. Это простейшая схема открытой адресации, при которой a_i= g(f(k), i) = f(k) + с*i, где с константа. Наиболее простая схема при с = 1.

Чтобы избежать первичного скучивания записей, с и N должны быть взаимно простыми, а с — не очень малым числом. Эта схема работает хорошо, пока таблица не слишком заполнена но по мере заполнения процесс замедляется.

При с = 1 среднее число проб при неудачном поиске равно: 0.5*(1 + (1 - к)-2), а при удачном 0.5*(1 + 1/(1 - к)), где к — коэффициент заполнения таблицы.

Квадратичная открытая адресация. При квадратичной адресации a_i = g(f(k), i) =f(k) + c*i + d*i², где с u d — константы. Число, проб здесь меньше, однако при почти заполненной таблице не удается избежать вторичного скучивания, когда при большом числе ключей синонимы одной группы вступают в коллизию с другими ключами.

Открытая адресация с двойным хешированием. По этой схеме а_i = g(f(k), i) = f{k) + i*h(k), где h(k) — хеш-функция, почти такая же, что и f(к), но не эквивалентная ей. Возможны различные варианты f(k) и h(k). Например, если N — простое число и f(k) = kmodN, то можно взять h(k) = 1 + kmod(N - 2), т.е. а_i = g(f(k), i) = kmodN + i*(1 + k*mod(N - 2)). В этом случае, функции f(к) и h(k) являются «независимыми» в том смысле, что на различных ключах значения обеих функций f и h совпадают с вероятностью O(1/N²), а не O(1/N).

Среднее число проб при неудачном поиске равно 1/(1 - к), а при удачном 1/k*ln(1/(1 - к)), к — коэффициент заполнения таблицы. Если функция h(k) зависит от f(k), то вторичные скучивания вызывают увеличение средних значений.