Рассмотрите хеш-таблицу со 100 слотами. Столкновения разрешаются с помощью цепочки. Предполагая простое равномерное хеширование, какова вероятность того, что первые 3 слота не будут заполнены после первых 3 вставок?
A) (97 × 97 × 97)/100³
B) (99 × 98 × 97)/100³
C) (97 × 96 × 95)/100³
D) (97 × 96 × 95)/(3! × 100³)
Решение :
А) правильно.
Простая универсальная хеш-функция — это гипотетическая хэш-функция, которая равномерно распределяет элементы по слотам хеш-таблицы. Более того, каждый элемент, подлежащий хешированию, имеет равную вероятность быть помещенным в слот, независимо от уже размещенных других элементов.
Probability that the first 3 slots are unfilled after the first 3 insertions = (probability that first item doesn't go in any of the first 3 slots)*(probability that second item doesn't go in any of the first 3 slots)*(probability that third item doesn't go in any of the first 3 slots)
= (97/100) * (97/100) * (97/100)
Спасибо за прочтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
