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

Метод открытой адресации предполагает несколько иной подход.
Имеется обычная хеш-таблице. В процессе ее заполнения, при получении нового значения, мы его заносим в том случае, если данная ячейка еще не заполнена (например, значение равно нулю). В противном случае предполагается занесение значения в другую ячейку, вычисляемую по какому-либо алгоритму, но если и она оказывается уже заполненной, то вычисляется еще одна ячейка и т.д.
Очевидно, что на самом деле существует столько конкретных методов открытой адресации, сколько алгоритмов перевычисления ячеек можно предложить.
Один из таких подходов называется методом линейных проб. Этот метод предполагает для вычисления заполняемой ячейки в случае коллизии использование функций:
 

h(x)=x mod q + 1; hi(x) = (x+1) mod q + 1; h₂(x) = (x+2) mod q + 1; h₃(x) = (x+3) mod q + 1;

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

Очевидно, что эффективность метода тем выше, чем меньше ячеек прихо­дится просмотреть при заполнении и поиске. Метод линейной адресации оказыва­ется неэффективным, так как данные часто имеют свойства группироваться вокруг определенных значений. Например, возраст преподавателей, может группи­роваться либо в пределах 50-60 лет, либо 25-30 лет, и подобные закономерности часты. Таким образом, при переадресации внутри хеш-таблицы следует стремить­ся к максимальному расширению области затрагиваемых ячеек.

Метод квадратичных проб состоит в том, что если возникает коллизия, ис­пользуем функции

h(x)=x mod q + 1; h₁(x) = (x+1) mod q + 1; h₂(x) = (x+2²) mod q + 1; h₃(x) = (x+3²) mod q + 1;

Здесь обязательно выполнение условия «простоты» числа q, иначе алгоритм, как доказано, может зациклить. Этот метод устраняет основной недостаток метода линейных проб и является наиболее часто используемым.