Изменения

Перейти к: навигация, поиск

Обсуждение участника:Kurkin

11 байт добавлено, 20:29, 6 июня 2015
Нет описания правки
Пусть мы ищем ключ <tex>D</tex>. Смотрим в его каноническую ячейку <tex>Dq</tex>. Если бит занятости не единица, то элемент точно не содержится в множестве.
Если бит занятости единица, то нам нужно найти пробег для <tex>Dq</tex>. Так как начало нужного пробега может быть сдвинуто, найдем начало кластера. Идем влево от ячейки <tex>Dq</tex> и ищем первую с битом сдвига равным нулю, эта ячейка и будет началом кластера. Пока мы идем влево от <tex>Dq</tex> будем поддерживать счетчик, который бедет показывать сколько пробегов нам нужно будет пропустить от начала кластера. Каждая ячейка с битом занятости равным единице увеличивает счетчик на <tex>1</tex>. После того как мы нашли начало кластера, пойдем от него в лево, каждая ячейка с битом продолжения равным нулю говорит о завершении пробега, когда счетчик станет равным нулю мы найдем нужный нам пробег для <tex>Dq</tex>. Если в этом пробеге содержится <tex>Dr</tex>, то <tex>D</tex> ,вероятно, содержится в множестве, иначе <tex>D</tex> точно не содержится в множестве.
=== Вставка ===
41
правка

Навигация