短链接生成算法

短链接生成

业务需求中经常会出现在短信中发送链接信息，存在一些链接长度太长，导致短信发送失败。 另外短信服务商收费是根据短信内容收费，链接越长短信收费也就越多； 所以短链接服务就很重要 ，需要把业务的长地址链接映射成短链接； 客户访问短链接时再重定向到原始的长链接来达成要求；

下面是java实现的端链接算法

import org.apache.commons.codec.binary.Hex;

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.UUID;

public class ShortLinkGenerator {

    /**
     * 所有字符集， url安全字符，不会被转义
     */
    private static final char[] CHARS = new char[]{
            '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',
            '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'
    };

    /**
     * 字符集长度，多进制表示
     */
    private static final int BASE = CHARS.length;
    /**
     * 生产短链接的长度
     */
    private static final int SHORT_LINK_LENGTH = 8;

    /**
     * hash冲突是声随机生成salt的长度
     */
    private static final int SALT_LENGTH = 6;

    /**
     * 随机数生成器
     */
    private static final SecureRandom random = new SecureRandom();

    /**
     * 生成随机盐
     *
     * @return
     */
    public static String generateSalt() {
        StringBuilder salt = new StringBuilder(SALT_LENGTH);
        for (int i = 0; i < SALT_LENGTH; i++) {
            int index = random.nextInt(CHARS.length);
            salt.append(CHARS[index]);
        }
        return salt.toString();
    }

    /**
     * 生成短链接
     *
     * @param url
     * @return
     */
    private static String generateShortLink(String url) {
        try {
            // 使用SHA-256哈希函数
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hashBytes = digest.digest(url.getBytes());

            // 将哈希值转换为多进制字符串
            String baseStr = hashToBaseMulti(hashBytes);

            // 确保字符串长度为8位
            return baseStr.substring(0, SHORT_LINK_LENGTH);
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("SHA-256 algorithm not found", e);
        }
    }

    /**
     * 生成短链接，加盐的方式
     *
     * @param url
     * @param salt
     * @return
     */
    private static String generateShortLinkWithSalt(String url, String salt) {
        try {
            url = url + salt;
            // 使用SHA-256哈希函数
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hashBytes = digest.digest(url.getBytes());

            // 将哈希值转换为进制字符串
            String baseStr = hashToBaseMulti(hashBytes);

            // 确保字符串长度为8位
            return baseStr.substring(0, SHORT_LINK_LENGTH);
        } catch (Exception e) {
            throw new RuntimeException("生成短链接异常", e);
        }
    }

    /**
     * 将哈希值转换为多进制字符串
     *
     * @param hashBytes
     * @return
     */
    private static String hashToBaseMulti(byte[] hashBytes) {
        // 使用BigInteger来避免负数问题
        BigInteger num = new BigInteger(1, hashBytes);
        StringBuilder baseStr = new StringBuilder();

        if (num.compareTo(BigInteger.ZERO) <= 0) {
            // 出现负数 直接用sha256的值， 测试未出现负数情况
            String str = Hex.encodeHexString(hashBytes);
            num = null;
            return str;
        }

        // 将大整数转换为多进制
        while (num.compareTo(BigInteger.ZERO) > 0) {
            BigInteger[] divRem = num.divideAndRemainder(BigInteger.valueOf(BASE));
            baseStr.append(CHARS[divRem[1].intValue()]);
            num = divRem[0];
        }

        // 如果生成的字符串长度不足8位，进行填充
        while (baseStr.length() < SHORT_LINK_LENGTH) {
            // 重复
            baseStr.append(baseStr);
        }
        num = null;
        // 由于上面是从低位到高位，需要反转
        return baseStr.reverse().toString();
    }

    public static long reverseBaseToDecimal(String input) {
        long result = 0;
        int power = input.length() - 1;
        for (char c : input.toCharArray()) {
            int index = getIndex(c);
            result += index * Math.pow(BASE, power);
            power--;
        }
        return result;
    }

    public static int getIndex(char c) {
        for (int i = 0; i < CHARS.length; i++) {
            if (CHARS[i] == c) {
                return i;
            }
        }
        throw new IllegalArgumentException("Invalid character: " + c);
    }

    public static void main(String[] args) {
        String s = generateShortLink("1");
        while (true) {
            System.out.println(generateShortLink(UUID.randomUUID().toString()));
        }
    }
}

测试输出

vGGAjErZ
Su2eWLuo
KyZ2J3P1
ikq0oQpy
d9ghFeU5
Yylh3Buu
DLqpzq9K
xdyDTG1h
exGAIWmF
iA8oPHY3
gkX9L96F
OvtVYSuc
ln5NkrOw
5FzvMOzT
vp3TfKqq
gVFcHevY
dVIKizG3
YlMv3Msx
ryHOLnaH
6awUTwj6
pwe2uBGx
5Moa9BME
HnNMpjUn
IIkBICM5
V6mMA03m
hpeNuGzl
LWsNzL9U
y1yKfmKR
7T9kdcdg
ZzsrKlCm

最终实测 hash碰撞率 千万分之三， 性能17w/s , 能满足常规业务要求

以上仅为算法实现，如完整短链服务，还需要处理hash冲突情况；