Google Reader

一次数学式的抓虫经历

by snnn

at 2012-09-14 21:55:03

original http://www.udpwork.com/item/8114.html

我们这有一个http service，每次应答的时候，它会生一个长度为8的随机字符串发给client。我们假设这个字符串是不会重复的，所以我们把它作为request id来唯一标识一个http request。但是后来做日志分析的时候，我们经常发现这个字符串重复了。

然后我去翻代码，发现有段代码有问题：

   static char[] alpha = ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXZY"
           +"0123456789abcdefghijklmnopqrstuvwxzy").toCharArray();

    static String getRandStr(int length) {
        char[] ret = new char[length];
        for (int i = 0; i != length; ++i) {
            int pos = ThreadLocalRandom.current().nextInt(alpha.length);
            ret[i] = alpha[pos];
        }
        return new String(ret);
    }

我第一眼就发现，0123456789被写了两遍。但是问题是，这究竟是BUG的真正原因吗？

我们这个页面每天要处理200万次请求，如果是从0-9、a-z、A-Z这62个字符随机，那么有效的取值范围是\( 62^8 \),约等于200万亿，根据我之前blog中介绍的公式 \(p = 1- e ^ {-\frac{m(m-1)}{2n}} \) 那么可计算出产生冲突的概率(p)小于百分之一。

但是上面的代码写错了，导致0-9的出现概率增大了一倍，为0.28。我不知道这种情况下该怎么算冲突概率，于是我就想用信息熵的方式模拟，len = 10 *.2777777778 + 52*(1-.2777777778)= 40.3。然后用40.3代替上面的62，计算出来冲突概率是25%。然后我写代码模拟了一下，

         public static void main(String[] args) {
        java.util.HashSet results = new java.util.HashSet();
        int badcount = 0;
        for (int j = 0; j != 20; ++j) {
            results.clear();
            for (int i = 0; i != 2000000; ++i) {
                if (!results.add(getRandStr(8))) {
                    badcount++;
                    break;
                }
            }
        }
        System.out.println(((double) badcount) / 20);
    }

发现结果基本吻合。

关于那个冲突概率的计算公式的推导过程请见：http://www.sunchangming.com/blog/?p=4141

        <div style="margin-top:8px;padding:6px 0;border-top:1px solid #3cf">
            <div style="text-align:center;margin:16px 0;padding:6px;border:0px dashed #999;font-family:arial;font-size:26px;font-weight:bold">
<a href="http://www.udpwork.com/item/8114.html#review_form" title="不喜欢" style="text-decoration:none">
    <img src="http://www.udpwork.com//images/thumb_down24.gif" alt="">
    <span style="color:#f33">0</span>
</a>
   
<a href="http://www.udpwork.com/item/8114.html#review_form" title="喜欢" style="text-decoration:none">
    <img src="http://www.udpwork.com//images/thumb_up24.gif" alt="">
    <span style="color:#3c3">0</span>
</a>