短链服务问题解决方案-短链码生成解决方案 —— (难度:无,等级:0)

DBC 109 0
温馨提示

本大模块难度级别为:无、简单、低、一般、中、较高、高

一、简单介绍 MurMurHash

  • 哈希算法:将一个元素映射成另一个元素
    • 加密哈希,如SHA256、MD5
    • 非加密哈希,如MurMurHash,CRC32
  • MurMurHash
    • Murmur哈希是一种非加密散列函数,适用于一般的基于散列的查找。
      它在2008年由Austin Appleby创建,在Github上托管,名为“SMHasher” 的测试套件。
      它也存在许多变种,所有这些变种都已经被公开。
      该名称来自两个基本操作,乘法(MU)和旋转(R)
    • 是一种【非加密型】哈希函数且【随机分布】特征表现更良好
    • 由于是非加密的哈希函数,性能会比MD5强
    • 再很多地方都用到比如Guava、Jedis、HBase、Lucence等
    • 存在两个版本
      • MurmurHash2(产生32位或64位值)
      • MurmurHash3(产生32位或128位值)
    • 数据量
      • MurmurHash的 32 bit 能表示的最大值近 43 亿的10进制
        • 满足多数业务,如果接近43亿则冲突概率大
  • MurMurHash得到的数值是10进制,一般会转化为62进制进行缩短
  • 常规短链码是6~8位数字+大小写字母组合

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

6 位 62 进制数可表示 568 亿个短链(62的6次方,每位都有62个可能,如果扩大位数到7位,则可以支持3万5200亿)

  • MurmurHash的 32 bit 满足多数业务 43亿
    • 拼接上库-表位则可以表示更多数据
    • 7位则可以到到 43亿 * 62 = 2666亿
    • 8位则可以到到 2666亿 * 62 = 1.65万亿条数据
    • 结合短链过期数据归档,理论上满足未来全部需求了
  • 数据库存储
    • 单表1千万 * 62个库 * 62表 = 384亿数据

二、代码封装

封装MurmurHash

    /**
     * 算法生成
     * @param param
     * @return
     */
    public static long murmurHash32(String param){
        long murmur3_32 = Hashing.murmur3_32().hashUnencodedChars(param).padToLong();
        return murmur3_32;
    }

10进制转62位进制、生成短链码

package net.dbc.component.component;

import net.dbc.utils.CommonUtil;
import org.apache.kafka.common.protocol.types.Field;
import org.springframework.stereotype.Component;

/**
 * @author DBC
 * @version 1.0.0
 * @date 2022年11月26日 17:14:01
 * @website dbc655.top
 */
@Component
public class ShortLinkComponent {


    /**
     * 62个字符
     */
    private static final String CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";


    /**
     * 生成短链码
     * @param param
     * @return
     */
    public String createShortLinkCode(String param){

        long murmurhash = CommonUtil.murmurHash32(param);
        //进制转换
        String code = encodeToBase62(murmurhash);

        return code;
    }

    /**
     * 10进制转62进制
     * @param num
     * @return
     */
    private String encodeToBase62(long num){

        // StringBuffer线程安全,StringBuilder线程不安全
        StringBuffer sb = new StringBuffer();
        do{
            int i = (int )(num%62);
            sb.append(CHARS.charAt(i));
            num = num/62;
        }while (num>0);

        String value = sb.reverse().toString();
        return value;

    }
}

简单测试

@RunWith(SpringRunner.class)
@SpringBootTest(classes = LinkApplication.class)
@Slf4j
public class ShortLinkTest {

    @Autowired
    private ShortLinkComponent shortLinkComponent;


    /**
     * 测试短链平台
     */
    @Test
    public void testCreateShortLink() {

        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            int num1 = random.nextInt(10);
            int num2 = random.nextInt(10000000);
            String originalUrl = num1 + ".dbc655" + num2 + ".top";
            String shortLinkCode = shortLinkComponent.createShortLinkCode(originalUrl);
            log.info("originalUrl:" + originalUrl + ", shortLinkCode=" + shortLinkCode);
        }
    }

}
运行效果图

短链服务问题解决方案-短链码生成解决方案 —— (难度:无,等级:0)插图

相信很容易看出来,原地址和生成后的短链地址,非常简洁[aru_12]

三、组件ShortLinkComponent疑惑

  • 为什么要用62进制转换,不是64进制?
    • 62进制转换是因为62进制转换后只含数字+小写+大写字母
    • 而64进制转换会含有/、+这样的符号(不符合正常URL的字符)
    • 10进制转62进制可以缩短字符,如果我们要6位字符的话,已经有560亿个组合了
  • 看业务情况有些短链也会加入其它特殊字符
    • 短链固定6位?肯定不是的,后续会进行分库分表改造

发表评论 取消回复
表情 图片 链接 代码

分享