个人中心
gpt4 book ai didi

java短网址服务(TinyURL)生成算法

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java短网址服务(TinyURL)生成算法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

前不久做了一个优惠劵的分享功能，其中一个功能就是生成一个优惠劵分享短链接。生成的短链接要求每个链接都是唯一的，并且长度尽可能短。在网上查了一下相关的思路，发现了一个不错的算法。这个算法的思路就是用[a-za-z0-9]建立一个长度为62的矩阵，然后把矩阵打乱，再生成一个全局唯一的数字，再把这个数字用矩阵内的元素表示转换成62进制,生成的链接长度最大才11位。所以短链接的生成关键点就变成了如何生成一个全局唯一的数字和实现进制的转换.

1、生成全局唯一的数字 。

这本质是一个分布式id的问题。如果简单处理的话可以借用redis的incr操作这样每次取到的id都是单调递增且唯一的。另外一种方式是借用mysql,这里不是借用mysql的主键的auto_incr特性。而是每一台应用来请求时分配一个范围比如 s1 [100-200], s2 来请求的时候就分配 [201-301]，本质是利用乐观锁进行一个cas操作.

如果不想借助外部去生成id的话，可以用uuid算法。uuid长度12个字节组成由，以下几个部分组成.

  • 4个字节表示的unix timestamp,
  • 3个字节表示的机器的id
  • 2个字节表示的进程id
  • 3个字节表示的计数器

uuid是一类算法的统称，具体有不同的实现。优点是每台机器可以独立产生id，理论上保证不会重复，所以天然是分布式的，缺点是生成的id太长，不仅占用内存，而且索引查询效率低.

还有一个叫twitter snowflake算法，本质上看起来与uuid有些类似。  。

java短网址服务(TinyURL)生成算法

总的来说redis,mysql解决方案就比较简单直接可以满足大部分的场景，如果要保证高性能和高可用的话uuid和twitter snowflake算法就更合适，实现起来相对复杂一些。   。

2、进制转换 。

这个操作就相对简单了。直接上代码:

java" id="highlighter_202171">
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
  * 短链接生成
  */
public class tinyurl {
 
   public static final char [] array =
           { '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' ,
           'q' , 'w' , 'e' , 'r' , 't' , 'y' , 'u' , 'i' , 'o' , 'p' , 'a' , 's' , 'd' ,
           'f' , 'g' , 'h' , 'j' , 'k' , 'l' , 'z' , 'x' , 'c' , 'v' , 'b' , 'n' , 'm' ,
           'q' , 'w' , 'e' , 'r' , 't' , 'y' , 'u' , 'i' , 'o' , 'p' , 'a' , 's' , 'd' ,
           'f' , 'g' , 'h' , 'j' , 'k' , 'l' , 'z' , 'x' , 'c' , 'v' , 'b' , 'n' , 'm' };
 
   public static map<character, integer> charvaluemap = new hashmap<character, integer>();
 
   //初始化map
   static {
     for ( int i = 0 ; i < array.length; i++) charvaluemap.put(array[i], i);
   }
 
 
   public static void main(string[] args) {
     for ( int i = 0 ; i < 100 ; i++) {
       long number = long .max_value - i;
       string decimalstr = numberconverttodecimal(number, 62 );
       system.out.println(number + " 转换成 " + decimalstr);
       long tonumber = decimalconverttonumber(decimalstr, 62 );
       system.out.println(decimalstr + " 转换成 " + tonumber);
     }
   }
 
 
   /**
    * 把数字转换成相对应的进制,目前支持(2-62)进制
    *
    * @param number
    * @param decimal
    * @return
    */
   public static string numberconverttodecimal( long number, int decimal) {
     stringbuilder builder = new stringbuilder();
     while (number != 0 ) {
       builder.append(array[( int ) (number - (number / decimal) * decimal)]);
       number /= decimal;
     }
     return builder.reverse().tostring();
   }
 
   /**
    * 把进制字符串转换成相应的数字
    * @param decimalstr
    * @param decimal
    * @return
    */
   public static long decimalconverttonumber(string decimalstr, int decimal) {
     long sum = 0 ;
     long multiple = 1 ;
     char [] chars = decimalstr.tochararray();
     for ( int i = chars.length - 1 ; i >= 0 ; i--) {
       char c = chars[i];
       sum += charvaluemap.get(c) * multiple;
       multiple *= decimal;
     }
     return sum;
   }
 
 
}

这里面有个小优化就是用charvaluemap记录每个字符对应的数值，这是一个用空间换时间的策略优化，把o(n)的时间降为o(1).

另外通常我们要记录短网址与长网址的对应的关系，相对于直接存储短网址的而言，存储对应的数值id会更省空间.

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

最后此篇关于java短网址服务(TinyURL)生成算法的文章就讲到这里了,如果你想了解更多关于java短网址服务(TinyURL)生成算法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： 详解IDEA2020新建spring项目和c3p0连接池的创建和使用
文章推荐： RSA实现JS前端加密与PHP后端解密功能示例
文章推荐： Java之Springcloud Gateway内置路由案例讲解
文章推荐： thinkPHP5框架接口写法简单示例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com