在哈希表中需要有多少个元素才能强制11路碰撞？

Question

我正在解决这个问题：

您有一个大小为100的散列表。需要散列到哈希表的最少元素数是多少，这样至少有11个元素可以保证具有相同的哈希值，而不管哈希函数如何？

据我说，应该是111，因为有100个唯一的可能的散列值；如果其中的11个被保证具有相同的散列，那么它应该是100 + 11 = 111。

然而，给出的答案是1001。

我的答案正确吗？若否，原因为何？

Answer 1

假设您的哈希表具有世界上最愚蠢的哈希函数，只需接受输入并对其进行100的调制。

现在，在表格中插入元素1、2、3、…、111。在100个插槽中，每个插槽将有多少个元素？

要了解1001从何而来，请以不同的方式考虑这个问题。在一个哈希表中可以插入多少个元素，这样每个插槽都有少于11个元素？在其中再添加一个元素将迫使某些槽有11个元素。