短URL算法

php – Hash理解
PS:短网址服务,可能很多朋友都已经不再陌生,现在大部分微博、手机邮件提醒等地方已经有很多应用模式了。自从twitter推出短网址(shorturl),继之国内各大微博跟风,google公开goo.gl使用API,短网址之风愈演愈烈.不得不说这是一个新兴又一大热门web2.0服务.现收集整理短网址生成原理,算法举例,以及优劣比较,同时还介绍几个phper个人实现的!

  1. 算法原理-算法一

    1)将长网址md5生成32位签名串,分为4段, 每段8个字节;
    2)对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理;
    3)这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串;
    4)总的md5串可以获得4个6位串; 取里面的任意一个就可作为这个长url的短url地址;

    这种算法,虽然会生成4个,但是仍然存在重复几率!

            function shorturl($url='', $prefix='', $suffix='') {
                $base = array (
                'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
                'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
                'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
                'y', 'z', '0', '1', '2', '3', '4', '5');
                $hex = md5($prefix.$url.$suffix);
                $hexLen = strlen($hex);
                $subHexLen = $hexLen / 8;
                $output = array();
                for ($i = 0; $i < $subHexLen; $i++) {
                    $subHex = substr ($hex, $i * 8, 8);
                    $int = 0x3FFFFFFF & (1 * ('0x'.$subHex));
                    $out = '';
                    for ($j = 0; $j < 6; $j++) {
                        $val = 0x0000001F & $int;
                        $out .= $base[$val];
                        $int = $int >> 5;
                    }
                    $output[] = $out;
                }
                return $output;
            }
            $urls = shorturl('http://wangying.sinaapp.com/');
            var_dump($urls);
            
            function shorturl($url = '', $prefix = '', $suffix = '') {
                $base = array(
                    "a", "b", "c", "d", "e", "f", "g", "h",
                    "i", "j", "k", "l", "m", "n", "o", "p",
                    "q", "r", "s", "t", "u", "v", "w", "x",
                    "y", "z", "0", "1", "2", "3", "4", "5",
                    "6", "7", "8", "9", "A", "B", "C", "D",
                    "E", "F", "G", "H", "I", "J", "K", "L",
                    "M", "N", "O", "P", "Q", "R", "S", "T",
                    "U", "V", "W", "X", "Y", "Z");
                $hex = md5($prefix . $url . $suffix);
                $hexLen = strlen($hex);
                $subHexLen = $hexLen / 8;
                $output = array();
                for ($i = 0; $i < $subHexLen; $i++) {
                    $subHex = substr ($hex, $i * 8, 8);
                    $int = 0x3FFFFFFF &(1 * ('0x' . $subHex));
                    $out = '';
                    for ($j = 0; $j < 6; $j++) {
                        $val = 0x0000003D &$int;
                        $out .= $base[$val];
                        $int = $int >> 5;
                    }
                    $output[] = $out;
                }
                return $output;
            }
            
  2. 算法二

    a-zA-Z0-9 这64位取6位组合,可产生500多亿个组合数量.把数字和字符组合做一定的映射,就可以产生唯一的字符串,如第62个组合就是aaaaa9,第63个组合就是aaaaba,再利用洗牌算法,把原字符串打乱后保存,那么对应位置的组合字符串就会是无序的组合。
    把长网址存入数据库,取返回的id,找出对应的字符串,例如返回ID为1,那么对应上面的字符串组合就是bbb,同理 ID为2时,字符串组合为bba,依次类推,直至到达64种组合后才会出现重复的可能,所以如果用上面的62个字符,任意取6个字符组合成字符串的话,你的数据存量达到500多亿后才会出现重复的可能。
    具体参看这里彻底完善新浪微博接口和超短URL算法,算法四可以算作是此算法的一种实现,此算法一般不会重复,但是如果是统计的话,就有很大问题,特别是对域名相关的统计,就抓瞎了


参考:
1.微博短链接算法php版本实现代码
2.
彻底完善新浪微博接口和超短URL算法

3.
微博URL短网址生成算法原理及(java版、php版实现实例)

3.
微博短网址生成算法原理

相关文章
  1. $_GET,$_POST与urldecode的使用风险
  2. yii2框架的错误处理
  3. Yii2过滤器-behaviors()行为调用
  4. 密码保护:PHP多进程编程
  5. 全排列算法原理和实现
  6. PHP静态方法和非静态方法的使用场景
本站版权
1、本站所有主题由该文章作者发表,该文章作者与尘埃享有文章相关版权
2、其他单位或个人使用、转载或引用本文时必须同时征得该文章作者和尘埃的同意
3、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
4、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意
5、原文链接:
二维码
Posted in php, 算法, 编程语言
Comments are closed.