专栏首页码匠的流水账聊聊base62与tinyURL

聊聊base62与tinyURL

base64大家肯定是很熟悉了,那base62是什么东东,它常被用来做短url的映射。

ascii编码的62个字母数字

Value Encoding  Value Encoding  Value Encoding  Value Encoding
  0 a            17 r            34 I            51 Z
  1 b            18 s            35 J            52 0
  2 c            19 t            36 K            53 1
  3 d            20 u            37 L            54 2
  4 e            21 v            38 M            55 3
  5 f            22 w            39 N            56 4
  6 g            23 x            40 O            57 5
  7 h            24 y            41 P            58 6
  8 i            25 z            42 Q            59 7
  9 j            26 A            43 R            60 8
 10 k            27 B            44 S            61 9
 11 l            28 C            45 T
 12 m            29 D            46 U
 13 n            30 E            47 V
 14 o            31 F            48 W
 15 p            32 G            49 X
 16 q            33 H            50 Y

26个小写字母+26个大写字母+10个数字=62

    public static final String BASE_62_CHAR = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    public static final int BASE = BASE_62_CHAR.length();

62进制与十进制的映射

62进制转10进制

还记得二进制转十进制的算法么,从右到左用二进制的每个数去乘以2的相应次方,次方要从0开始。62进制转10进制也类似,从右往左每个数*62的N次方,N从0开始。

    public static long toBase10(String str) {
        //从右边开始
        return toBase10(new StringBuilder(str).reverse().toString().toCharArray());
    }

    private static long toBase10(char[] chars) {
        long n = 0;
        int pow = 0;
        for(char item: chars){
            n += toBase10(BASE_62_CHAR.indexOf(item),pow);
            pow++;
        }
        return n;
    }

    private static long toBase10(int n, int pow) {
        return n * (long) Math.pow(BASE, pow);
    }

十进制转62进制

还记得十进制转二进制的算法么,除二取余,然后倒序排列,高位补零。转62进制也类似,不断除以62取余数,然后倒序。

    public static String fromBase10(long i) {
        StringBuilder sb = new StringBuilder("");
        if (i == 0) {
            return "a";
        }
        while (i > 0) {
            i = fromBase10(i, sb);
        }
        return sb.reverse().toString();
    }

    private static long fromBase10(long i, final StringBuilder sb) {
        int rem = (int)(i % BASE);
        sb.append(BASE_62_CHAR.charAt(rem));
        return i / BASE;
    }

短url的转换

主要思路,维护一个全局自增的id,每来一个长url,将其与一个自增id绑定,然后利用base62将该自增id转换为base62字符串,即完成转换。

public class Base62UrlShorter {

    private long autoIncrId = 10000;

    Map<Long, String> longUrlIdMap = new HashMap<Long, String>();

    public long incr(){
        return autoIncrId ++ ;
    }

    public String shorten(String longUrl){
        long id = incr();
        //add to mapping
        longUrlIdMap.put(id,longUrl);
        return Base62.fromBase10(id);
    }

    public String lookup(String shortUrl){
        long id = Base62.toBase10(shortUrl);
        return longUrlIdMap.get(id);
    }
}

测试

    @Test
    public void testLongUrl2Short(){
        Base62UrlShorter shorter= new Base62UrlShorter();
        String longUrl = "https://movie.douban.com/subject/26363254/";
        String shortUrl = shorter.shorten(longUrl);
        System.out.println("short url:"+shortUrl);
        System.out.println(shorter.lookup(shortUrl));
    }

关于容量

自增id为long型,最大2^64 -1

doc

  • 534. Design TinyURL
  • 如何设计短网址系统(TinyURL)

本文分享自微信公众号 - 码匠的流水账(geek_luandun)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java降低竞争锁的一些方法

    本文介绍一下提升并发可伸缩性的一些方式:减少锁的持有时间,降低锁的粒度,锁分段、避免热点域以及采用非独占的锁或非阻塞锁来代替独占锁。

    codecraft
  • 聊聊skywalking的spring-annotation-plugin

    本文主要研究一下skywalking的spring-annotation-plugin

    codecraft
  • 聊聊debezium的SimpleSourceConnector

    debezium-v1.1.1.Final/debezium-embedded/src/main/java/io/debezium/connector/simp...

    codecraft
  • asp.net与asp的session共享 及 asp的请求拦截

    asp.net 与 asp 的session是无法直接共享的(底层的处理dll也不一样),要想互通session,只能用变通的办法: 一、asp.net -> ...

    菩提树下的杨过
  • 【Python之旅】第六篇(三):Pyt

        学习Python的多线程(Multi-threading),至少应该要有进程与线程的基本概念,可以看我转载的一篇文章:《进程与线程的一个简单解释》。

    py3study
  • 面试官问线程安全的List,看完再也不怕了!

    下面给大家总结一下吧,栈长在之前的文章《出场率比较高的一道多线程安全面试题》里面也讲过 ArrayList 的不安全性。

    Java技术栈
  • Django ModelChoiceField:修改过滤查询集 queryset的两种方法

    Django Form类定义中有一个 ModelChoiceField  对应的是Model 的外键,queryset 是返回一个查询集对象

    KEVINGUO_CN
  • JPA 详解

    Java Persistence API(JPA)是将Java对象和关系型数据库对象映射起来规范。实现这个规范后开发者可以使用相同的代码可以在任意的数据库中执行...

    代码拾遗
  • 设计模式 - 模板模式 - JavaScript

    模板模式是:抽象父类定义了子类需要重写的相关方法。并且这些方法,仍然是通过父类方法调用的。

    心谭博客
  • 分享 | Charles 力助分析网络封包

    Charles是Mac平台下常用的调试工具,用来分析网络通信协议,这个功能在做移动端开发时非常有用,因为有时候你不得不通过抓包来分析通信定位问题,移动端开发跟W...

    icepy

扫码关注云+社区

领取腾讯云代金券