Java实现短网址服务：自增序列与MD5碰撞算法详解

远山来客

发布时间：2026-10-13 | 4人浏览过

原创

本文将深入探讨利用Java语言构建短网址（Short URL）服务核心的两种算法模型：无冲突的自增序列转换与高效的MD5哈希切片法。通过对比两者的数据映射机制与代码实现细节，解析如何在有限字符集下最大化存储容量并平衡查询性能。

结果或目标

短网址服务的核心目标是将较长的原始URL转换为极简短字符串，便于在社交媒体分享、短信传播等场景使用。在Java环境中实现这一功能，主要面临两个技术挑战：一是如何将长整型或哈希值映射为可读性强的短字符串；二是如何保证生成的短串唯一性或具备高效的去重检索能力。

准备条件

要实现上述两种算法，需要准备好以下基础环境与依赖：

运行环境：JDK 8及以上版本。
工具类库：commons-lang3用于处理字符串填充与子串截取，commons-codec或类似库用于生成MD5摘要。
字符集定义：短网址通常采用 0-9, a-z, A-Z 共62个字符作为进制转换的底表。

第1步：定义Base62字符映射表

目的：建立数字索引到可视字符的双向映射基础。

入口：通用工具类定义。

动作：按顺序声明包含数字和大小写字母的字符数组。这是所有进制转换操作的基础查找表。

static final char[] DIGITS = {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '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'
};

真实操作顺序

第2步：基于自增序列的62进制转换（推荐高并发场景）

目的：利用全局唯一的递增ID直接生成短码，确保零碰撞，适合大规模分布式部署。

入口：短网址生成核心方法。

动作：

获取唯一ID：使用 AtomicLong 保证多线程环境下ID的原子递增。在实际生产环境中，建议替换为 Snowflake 等分布式ID生成器。
进制转换：将长整型ID不断除以62取余数，根据余数从 DIGITS 数组中提取对应字符，反向拼接即为短网址。

private AtomicLong sequence = new AtomicLong(0);

@Override
protected String shorten(String longUrl) {
    // 1. 获取自增值 (实际应使用分布式ID生成器)
    long myseq = sequence.incrementAndGet();
    
    // 2. 转换为Base62字符串
    return to62RadixString(myseq);
}

private String to62RadixString(long seq) {
    StringBuilder sBuilder = new StringBuilder();
    while (true) {
        int remainder = (int) (seq % 62);
        sBuilder.append(DIGITS[remainder]);
        seq = seq / 62;
        if (seq == 0) {
            break;
        }
    }
    // 反转字符串以符合正常阅读顺序
    return sBuilder.reverse().toString();
}

第3步：基于MD5哈希的分片提取（节省存储空间）

目的：利用哈希函数的随机性将任意长度URL压缩为固定长度的短串，避免维护庞大的序列状态，适合单机或小规模服务。

入口：短网址生成方法 shorten(String longUrl, int urlLength)。

重要参数：urlLength 限制在1-6之间，分别对应不同的碰撞概率和容量上限。

动作：

计算MD5：对原始URL计算标准32位MD5十六进制字符串。
掩码处理：根据目标长度计算二进制掩码（如长度为3，则取18位有效数据），与MD5片段进行按位与操作，保留低位有效比特。
分片索引：将MD5字符串分为4段，每段处理后映射为指定长度的短串。遍历这4个候选结果，检查数据库中是否已存在该短串。若不存在，则返回并使用；若存在，尝试下一段。

public String shorten(String longUrl, int urlLength) {
    // 校验长度范围
    if (urlLength < 0 || urlLength > 6) {
        throw new IllegalArgumentException("the length of url must be between 0 and 6");
    }
    
    String md5Hex = DigestUtils.md5Hex(longUrl);
    int binaryLength = urlLength * 6;
    // 创建指定长度的全1二进制掩码，例如长度3需18位1
    long binaryLengthFixer = Long.valueOf(StringUtils.repeat("1", binaryLength), BINARY);
    
    for (int i = 0; i < 4; i++) {
        // 1. 取MD5第i段的8位十六进制字符串
        String subString = StringUtils.substring(md5Hex, i * 8, (i + 1) * 8);
        
        // 2. 转为long并与掩码做&运算，保留低位二进制
        long hexVal = Long.valueOf(subString, 16) & binaryLengthFixer;
        String binStr = Long.toBinaryString(hexVal);
        
        // 3. 左侧补零至binaryLength长度
        binStr = StringUtils.leftPad(binStr, binaryLength, "0");
        
        StringBuilder sbBuilder = new StringBuilder();
        // 4. 每6个比特映射为一个字符
        for (int j = 0; j < urlLength; j++) {
            String subPart = StringUtils.substring(binStr, j * 6, (j + 1) * 6);
            int index = Integer.valueOf(subPart, BINARY) & NUMBER_61;
            sbBuilder.append(DIGITS[index]);
        }
        
        String shortUrl = sbBuilder.toString();
        
        // 5. 查重：如果该短地址未指向任何长地址，则返回
        if (lookupLong(shortUrl) != null) {
            continue; // 发生碰撞，尝试下一个MD5分段
        } else {
            // 记录映射关系并返回
            return shortUrl;
        }
    }
    return null; // 四次尝试均碰撞，理论上极低概率
}

完成判断与排错

完成状态判断：

自增序列法：每次调用返回不同且递增的字符串。验证时需观察连续生成的短码是否按62进制规律演变（如...z9 -> ...zz -> ...00）。
MD5哈希法：相同输入永远返回相同输出。验证时需确认对于同一URL，无论重试多少次，只要数据库中存在即返回一致结果，新URL能成功生成短码并存入存储系统。

常见问题排查：

空指针异常：在使用 DigestUtils.md5Hex 前，请确保传入的 longUrl 非空且经过编码处理。
碰撞率过高：在MD5方案中，若 urlLength 过小（如1或2位），碰撞概率显著增加。建议至少设置为3位以上（62^3 ≈ 23万次）。若频繁遇到 return null，说明短码池即将耗尽，需增加长度。
并发一致性：自增序列如果使用本地 AtomicLong，在重启后会重置序列导致短码重复或断裂。生产环境务必对接数据库自增主键或Redis原子操作。