短链服务问题解决方案-短链码生成解决方案 —— （难度：无，等级：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进制进行缩短
  • 例子
    • 10进制：1813342104
    • 转62进制：1YIB7i
    • https://tool.lu/hexconvert/
• 常规短链码是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);
        }
    }

}

运行效果图

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

三、组件ShortLinkComponent疑惑

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