一种计数算法
内容提要
本文介绍了一种新的统计唯一元素的思路，采用了采样的方式。通过将一半的元素放入哈希表中保存，并增加随机率来降低内存占用。算法实现简单，思路开阔。
延伸解读
采样估算的直观类比
文章用“钓放标记鱼”来类比采样统计：先随机抽取一部分元素做标记，再根据标记元素的比例反推整体。这种思路将精确计数转化为概率估算，牺牲精度换取更低内存。读者可借此理解采样算法的核心——用部分推断整体，但需注意估算结果存在随机波动，不适合要求精确的场景。
重复元素带来的公平性问题
直接对每个元素独立随机决定是否放入哈希表，会导致出现次数多的元素被选中的概率更高，从而扭曲唯一元素数量的估计。文章指出，在随机前先删除该元素在哈希表中的旧记录，可消除历史出现次数的影响，使每个元素是否保留仅取决于最后一次随机结果。这一修正保证了采样的公平性。
动态调整随机率以控制内存
固定随机率下，哈希表大小仍与数组长度相关。文章提出动态方案：当哈希表元素数达到上限时，将随机率翻倍，并对已有元素再次随机剔除，使它们符合新的采样概率。这样内存占用可被限制在设定上限附近，但每次调整都会引入额外随机性，估算精度可能进一步下降。
适用场景与局限性
该算法实现简单，适合对内存敏感且允许误差的场合，如粗略统计唯一元素数量。但文章明确不建议在生产环境使用，因为其精度受随机率、数组长度和重复元素分布影响，且动态调整会累积误差。读者应将其视为一种开阔思路的示例，而非精确计数工具。
Q&A
统计数组中唯一元素个数，除了哈希表和排序，还有什么新思路？
文章提出一种基于采样的新思路：随机将一部分元素放入哈希表，最后用哈希表大小乘以采样率的倒数来估算唯一元素总数。这种方法牺牲精度以降低内存占用。
采样统计唯一元素时，为什么元素出现次数会影响公平性？如何解决？
因为元素每次出现都有机会被随机放入哈希表，出现次数越多，最终留在哈希表中的概率越大，导致估算偏差。解决方法是在每次随机前先将该元素从哈希表中删除，这样只有最后一次随机的结果决定其是否在哈希表中。
如何进一步降低采样统计唯一元素的内存占用？
可以增加随机率（即降低采样概率），例如使用 rand.Intn(p) == 0 来控制放入哈希表的概率，p 越大，哈希表中保存的元素越少，内存占用越低。
采样统计唯一元素的算法能否动态调整随机率以适应不同数组长度？
可以。文章给出一种动态调整方法：当哈希表大小达到 maxSize 时，将随机率 p 翻倍，并对哈希表中已有元素再次进行随机删除，使其符合新的随机率，从而控制内存上限。
采样统计唯一元素的方法适合在生产环境使用吗？
文章明确指出并不建议在生产环境中使用，但仍认为这是一种有启发的思路。
采样统计唯一元素的思路和统计湖泊中鱼的数量有什么关系？
文章用统计湖泊中鱼的数量来类比：先钓 n 条鱼做记号，几天后再钓 n 条鱼看其中有多少有记号，从而估算总数。采样统计唯一元素也是通过随机采样一部分元素来估算整体唯一元素数量。
