О хеш-таблице

Question

Хеш-функция h отображает 16-битные входы в 8-битные хеш-значения. Какая самая большая k такая, что в любом наборе 1000 входов, есть как минимум k входов, которые h отображаются на одно и то же значение хеша?

Я думаю, что k должно быть 3. Потому что 1000/256 = 3. ~ Однако ключ ответа - 4. Это экзамен GRE, поэтому я думаю, что ответ правильный. Может ли кто-нибудь помочь мне объяснить это?

Answer 1

Это 4, потому что вам нужно округлить до здесь.Есть 256 возможных выходов хеша;если вы получите не более 3 раз каждое выходное значение, то у вас будет максимум 256 * 3 = 768 входов.Таким образом, ответ 1000/256, округляется , следовательно, 4.