几个容器如何加载任意数字?

提供的是在$m^n$个机会中均匀随机选取的字母$\{1,2,\ldots,m\}$上的一系列$\langle a_1,a_2,\ldots,a_n\rangle$。 什么是预期的维度 $\{a_1,a_2,\ldots,a_n\}$?

如果$m=n$它是似乎,那么解决方案通常倾向于$(1-1/e)n$为$n\to\infty$,但我不知道为什么。

我在对哈希表的一些代码进行基准测试时遇到了这个问题,所以如果它是哈希地球的一个典型原因我不会感到震惊。

0
2019-05-13 03:35:22
资源 分享
答案: 2

如果字符串$i$存在于集合${a_1,\dots,a_n}$中,则将$1 \leq i \leq m$的指示任意变量$I_i$定义为$1$。 之后,集合的维度仅为$\sum_{i=1}^m I_i$。 可以通过假设的线性方便地计算这种假设。 $1-\left( \frac{m-1}{m} \right)^n$提供$1$的概率由$1-\left( \frac{m-1}{m} \right)^n$提供,因此预期的集合维度为$m \left[ 1- \left( 1 - \frac{1}{m} \right)^n \right]$。 对于$m=n$,限制值毫无疑问,正如您在查询中所述。

0
2019-05-17 14:59:39
资源
0
2019-05-17 13:52:11
资源