Случайный афоризм
Не тот поэт, кто рифмы плесть умеет. Александр Сергеевич Пушкин
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

     Замечание.  Более сильное требование к семейству H могло бы
состоять в том, чтобы для любых двух различных элементов s  и  t
множества  T  значения h(s) и h(t) случайной функции h являются
независимыми случайными величинами,  равномерно  распределенными
на 0..n-1.

     11.2.3. Пусть t[1]..t[u] - произвольная  последовательность
различных элементов множества T. Рассмотрим количество действий,
происходящих при помещении элементов t[1]..t[u] в множество, хе-
шируемое  с помощью функции h из универсального семейства H. До-
казать, что среднее количество действий (усреднение - по всем  h
из H) не превосходит C*u*(1+u/n).

     Решение. Обозначим через m[i] количество элементов последо-
вательности,   для   которых   хеш-функция   равна   i.   (Числа
m[0]..m[n-1] зависят, конечно,  от  выбора  хеш-функции.)  Коли-
чество действий, которое мы хотим оценить, с точностью до посто-
янного множителя равно сумме квадратов чисел m[0]..m[n-1]. (Если
k  чисел попадают в одну хеш-ячейку, то для этого требуется при-
мерно 1+2+...+k действий.) Эту же сумму квадратов можно записать
как число пар , для которых h[t[p]]=h[t[q]]. Последнее  ра-
венство,  если его рассматривать как событие при фиксированных p
и q, имеет вероятность 1/n при p<>q,  поэтому  среднее  значение
соответствующего члена суммы равно 1/n, а для всей суммы получа-
ем оценку порядка u*u/n, а точнее u*u/n + u, если учесть члены с
p=q.

   Оценка  этой  задачи  показывает, что в на каждый добавляемый
элемент  приходится  в среднем C*(1+u/n) операций. В этой оценке
дробь u/n имеет смысл "коэффициента заполнения" хеш-таблицы.

     11.2.4. Доказать аналогичное утверждение  для  произвольной
последовательности  операций добавления, поиска и удаления (а не
только для добавления, как в предыдущей задаче).

     Указание. Будем представлять себе, что в ходе  поиска,  до-
бавления  и удаления элемент проталкивается по списку своих кол-
лег с тем же хеш-значением, пока не найдет своего  двойника  или
не  дойдет  до  конца  списка.  Будем называть i-j-столкновением
столкновение t[i] с t[j]. Общее число  действий  примерно  равно
числу всех столкновений плюс число элементов. При t[i]<>t[j] ве-
роятность i-j-столкновения равна  1/n.  Осталось  проследить  за
столкновениями  между  равными  элементами.  Фиксируем некоторое
значение x из множества T и посмотрим на связанные с ним  опера-
ции.  Они  идут по циклу: добавление - проверки - удаление - до-
бавление - проверки - удаление -  ...  Столкновения  между  ними
происходят  между добавляемым элементом и следующими за ним про-
верками (до удаления включительно), поэтому общее  их  число  не
превосходит числа элементов, равных x.

     Теперь приведем примеры универсальных  семейств.  Очевидно,
для  любых конечных множеств A и B семейство всех функций, отоб-
ражающих A в B, является универсальным.  Однако  этот  пример  с
практической  точки зрения бесполезен: для запоминания случайной
функции из этого семейства нужен массив, число элементов в кото-
ром равно числу элементов в множестве A. (А если мы  можем  себе
позволить  такой массив, то никакого хеширования нам не требует-
ся!)

     Более практичные примеры универсальных семейств могут  быть

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 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.