Хэш-функции (Hash functions). Лекция 7

Слайд 6

(открытая адресация)

(закрытая адресация)

(открытая адресация) (закрытая адресация)

Слайд 12

Ключевые
Бесключевые

Ключевые Бесключевые

Слайд 15

Коллизия 2 рода
Пусть есть 5 объектов принимающих 10 значений.
Значения каких-то двух

Коллизия 2 рода Пусть есть 5 объектов принимающих 10 значений. Значения каких-то
объектов совпадают.
(Вероятность =?)

Коллизия 1 рода
Пусть есть 5 объектов принимающих 10 значений.
Значение конкретного элемента совпадает со значением другого элемента. (вероятность = 1/10)

Коллизия 2 рода

Слайд 17

Вероятность, того, что дни рождения не совпадут

Вероятность, того, что дни рождения совпадут

Какова

Вероятность, того, что дни рождения не совпадут Вероятность, того, что дни рождения
вероятность для 5-ти объектов с 10-ю вариантами значений?

Слайд 19

Приближение

При p(n)=1/2, N=365 количество человек составит

Приближение При p(n)=1/2, N=365 количество человек составит