Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[77]

Квадратичная последовательность проб

Функция, определяющая квадратичную последовательность

проб (quadratic probing), задаётся формулой

где по-прежнему Ы - обычная хеш-функция, а с\ и с2 ф 0 - некоторые константы. Пробы начинаются с ячейки номер T[h(k)], как и при линейном методе, но дальше ячейки просматриваются не подряд: номер пробуемой ячейки квадратично зависит от номера попытки. Этот метод работает значительно лучше, чем линейный, но если мы хотим, чтобы при просмотре хеш-таблицы использовались все ячейки, значения то, с\ и с2 нельзя выбирать как попало; один из способов выбора описан в задаче 12-4. Как и при линейном методе, вся последовательность проб определяется своим первым членом, так что опять получается всего то различных перестановок. Тенденции к образованию кластеров больше нет, но аналогичный эффект проявляется в (более мягкой) форме образования вторичных кластеров (secondary clustering).

Двойное хеширование

Двойное хеширование (double hashing) - один из лучших методов открытой адресации. Перестановки индексов, возникающие при двойном хешировании, обладают многими свойствами, присущими равномерному хешированию. При двойном хешировании функция h имеет вид

где h\ и h2 - обычные хеш-функции. Иными словами, последовательность проб при работе с ключом к представляет собой арифметическую прогрессию (по модулю то) с первым членом hi(k) и шагом h2(k). Пример двойного хеширования приведен на рис. 12.5.

Чтобы последовательность испробованных мест покрыла всю таблицу, значение h2(k) должно быть взаимно простым с то (если наибольший общий делитель h2(k) и то есть d, то арифметическая прогрессия по модулю то с разностью h2(k) займёт долю 1/d в таблице; см. главу 33). Простой способ добиться выполнения этого условия - выбрать в качестве то степень двойки, а функцию h2 взять такую, чтобы она принимала только нечётные значения. Другой вариант: то - простое число, значения h2 - целые положительные числа, меньшие то. Например, для простого то можно положить

h(k, г) = (hi(k) + ih2(k)) mod то,

hi(k) = к mod то, h2(k) = 1 + (к mod то)


Рис. 12.5 Добавление элемента в таблицу с открытой адресацией при двойном хешировании. В нашем случае т = 13, hi(k) = k mod 13, /гг(/с) = 1 + (/с mod 11). Если к = 14, то последовательность проб будет такая: 1 и 5 заняты, 9 свободно, помещаем туда.

где га чуть меньше, чем га (например, га = га - 1 или га - 2). Если, например, га = 701, га = 700 и к = 123456, то hi (к) = 80 и h,2(k) = 257. Стало быть, последовательность проб начинается с позиции номер 80 и идёт далее с шагом 257, пока вся таблица не будет просмотрена (или не будет найдено нужное место).

В отличие от линейного и квадратичного методов, при двойном хешировании можно получить (при правильном выборе hi и h) не га, а в (га2) различных перестановок, поскольку каждой паре (hi(k), h2(k)) соответствует своя последовательность проб. Благодаря этому производительность двойного хеширования близка к той, что получилась бы при настоящем равномерном хешировании.

Анализ хеширования с открытой адресацией

Так же, как и при анализе хеширования с цепочками, при анализе открытой адресации мы будем оценивать стоимость операций в терминах коэффициента заполнения а = п/т (п - число записей, га - размер таблицы). Поскольку при открытой адресации каждой ячейке соответствует не более одной записи, а 1.

Мы будем исходить из предположения о равномерности хеширования. В этой идеализированной схеме предполагается следующее: мы выбираем ключи случайным образом, причём все га! возможных последовательностей проб равновероятны. Поскольку эта идеализированная схема далека от реальности, доказываемые ниже результаты следует рассматривать не как математические теоремы, описывающие работу реальных алгоритмов открытой адресации,


а как эвристические оценки.

Начнём с того, что оценим время на поиск элемента, отсутствующего в таблице.

Теорема 12.5. Математическое ожидание числа проб при поиске в таблице с открытой адресацией отсутствующего в ней элемента не превосходит 1/(1 -а) (хеширование предполагается равномерным, через а < 1 обозначен коэффициент заполнения).

Доказательство. Мы предполагаем, что таблица фиксирована, а искомый элемент выбирается случайно, причём все возможные последовательности проб равновероятны. Нас интересует математическое ожидание числа попыток, необходимых для обнаружения свободной ячейки, то есть сумма

где pi - вероятность того, что мы встретим ровно г занятых ячеек.

Каждая новая проба выбирается равномерно среди оставшихся не испробованными ячеек; если разрешить пробовать повторно уже испробованные ячейки, то часть проб пропадёт зря и математическое ожидание только увеличится. Но для этого нового варианта мы уже вычисляли математическое ожидание (раздел 6.4, геометрическое распределение), и оно равно

поскольку вероятность успеха для каждой пробы равна 1 - а. □

Если коэффициент заполнения отделён от единицы, теорема 12.5 предсказывает, что поиск отсутствующего элемента будет в среднем проходить за время 0(1). Например, если таблица заполнена наполовину, то среднее число проб будет не больше 1/(1 - 0,5) = 2, а если на 90%, то не больше 1/(1 - 0,9) = 10.

Из теоремы 12.5 немедленно получается и оценка на стоимость операции добавления к таблице:

Следствие 12.6. В предположении равномерного хеширования математическое ожидание числа проб при добавлении нового элемента в таблицу с открытой адресацией не превосходит 1/(1 - а), где а < 1 - коэффициент заполнения.

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

оо

8 = 0

Оценить среднее время успешного поиска немногим сложнее.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]