面试速答（先看这里）

**一句话结论：**如果要不碰撞，可以用数据库或者Redis自增ID来实现也可以的，但是这么做的话，就有可能被穷举出来。

60秒标准回答：

把一个链接转成另外一个链接，方式很简单，有很多算法，比如MD5、SHA等等hash函数就可以，但是Hash函数存在着一定的碰撞风险

如果要不碰撞，可以用数据库或者Redis自增ID来实现也可以的，但是这么做的话，就有可能被穷举出来

那不想被穷举的话，还可以用类似雪花算法这种方式，但是雪花算法生成的id长度又太长了

**答题顺序：**结论 → 原理/机制 → 关键流程 → 场景与取舍 → 易错点

回答主线：

**为什么选择base62：**Base62 编码使用了 62 个字符，具体包括：
**MurmurHash的原理：**MurmurHash 将输入数据处理成固定大小的块（通常是 4 字节或 8 字节），然后对每个块进行一系列混合操作（mixing），最终生成哈希值。

**记忆锚点：**MurmurHash → Base62 → URL → 乘法 → Base64 → mixing

关键取舍：

MurmurHash 是一种哈希算法，因其高效的性能和良好的哈希分布，被广泛应用于需要快速哈希计算的场景，比如哈希表、分布式存储和数据去重。

易错提醒：

把一个链接转成另外一个链接，方式很简单，有很多算法，比如MD5、SHA等等hash函数就可以，但是Hash函数存在着一定的碰撞风险。
所以，我们想要把一个长连接转成短连接，并且有几个要求，还真不是一件容易的事儿：在行业内有一种比较常见的做法，那就是基于 MurmurHash+62进制转换的方式来实现。

加分表达：

如果要不碰撞，可以用数据库或者Redis自增ID来实现也可以的，但是这么做的话，就有可能被穷举出来。
处理剩余数据：如果数据的长度不是 4 的倍数（对于 32 位哈希），或者 8 的倍数（对于 64 位哈希），则需要单独处理剩余的字节。

追问准备：

围绕「MurmurHash」：底层原理是什么？使用时有哪些边界和常见坑？
围绕「Base62」：底层原理是什么？使用时有哪些边界和常见坑？
围绕「URL」：底层原理是什么？使用时有哪些边界和常见坑？
如果线上出现异常，你会如何定位、验证并规避？

典型回答

把一个链接转成另外一个链接，方式很简单，有很多算法，比如MD5、SHA等等hash函数就可以，但是Hash函数存在着一定的碰撞风险。

如果要不碰撞，可以用数据库或者Redis自增ID来实现也可以的，但是这么做的话，就有可能被穷举出来。

那不想被穷举的话，还可以用类似雪花算法这种方式，但是雪花算法生成的id长度又太长了。

所以，我们想要把一个长连接转成短连接，并且有几个要求，还真不是一件容易的事儿：

1、链接更短

2、不能重复

3、不能被穷举

在行业内有一种比较常见的做法，那就是基于****MurmurHash+62进制转换的方式来实现。

MurmurHash 是一种哈希算法，因其高效的性能和良好的哈希分布，被广泛应用于需要快速哈希计算的场景，比如哈希表、分布式存储和数据去重。 MurmurHash 使用了多轮混合操作（mixing）的方式，通过位移、乘法和异或操作，将输入数据混淆，生成一个分布均匀的哈希值。

在短链服务中，MurmurHash（读作：么么哈希）可以用来生成哈希值，将长 URL 转换为固定长度的哈希值作为短链地址的一部分。例如：

输入长 URL：https://www.hollischuang.com/archives/6998
计算哈希值：通过 MurmurHash3 算法生成哈希值。
转换为 Base62 编码：将哈希值转换为短链字符集（如 Base62）。
存储和查询：将短链和长 URL 的映射存入数据库。

plain

String longUrl = "https://www.hollischuang.com/archives/6998";
int hash = MurmurHash3.murmurhash3_x86_32(longUrl.getBytes(), seed);
String shortLink = base62Encode(hash);
storeInDatabase(shortLink, longUrl);

输出结果大致为： 8M0kX 这样的字符串内容，就是一个我们想要的短链。

扩展知识

为什么选择base62

Base62 编码使用了 62 个字符，具体包括：

数字：0-9 （10 个字符）
大写字母：A-Z （26 个字符）
小写字母：a-z （26 个字符）

相比于 Base64（64 个字符，包括字母、数字和特殊字符），Base62 编码去掉了+和/等特殊字符，只保留字母和数字，这使得它更加适合在 URL 中使用，因为许多 URL 系统可能不允许或不适应某些特殊字符。Base62 编码仅使用字母和数字字符，它们在所有环境中都能安全使用。

MurmurHash的原理

（这块可以不用看）

MurmurHash 将输入数据处理成固定大小的块（通常是 4 字节或 8 字节），然后对每个块进行一系列混合操作（mixing），最终生成哈希值。以下是 MurmurHash 算法的基本步骤：

初始化哈希值：哈希值通常使用一个“种子”值进行初始化，种子值可以是固定的常量，也可以是用户传入的参数。种子的作用是使得同一数据在不同的执行中产生不同的哈希值。
处理每个数据块：

将输入数据按块分割为多个 4 字节（32 位）或 8 字节（64 位）的块。
对每个块执行混合操作。混合操作通常包括：
乘法：将块中的每个值与一个常数相乘。
旋转（rotate）：通过位移操作将值进行旋转（例如，左旋转 15 位）。
异或（XOR）：将当前的哈希值与块的处理结果进行异或操作。

处理剩余数据：如果数据的长度不是 4 的倍数（对于 32 位哈希），或者 8 的倍数（对于 64 位哈希），则需要单独处理剩余的字节。
最后的混合（Final Mixing）：在所有数据块处理完毕后，还需要对结果执行一些最终的混合操作，以确保哈希值的均匀分布：

异或：将哈希值与它自身的右移进行异或。
乘法：再次与一个常数相乘，增强扰动性。
右移：使用右移操作来进一步扰乱结果。

返回最终哈希值：经过所有的混合和扰乱操作后，最终得到的值即为输入数据的哈希值。

乘法和旋转能有效打乱输入数据的结构，增加数据的“随机性”。

异或操作确保每一部分数据都对最终哈希值产生影响。

最后的混合操作是为了减少哈希碰撞的概率，并且进一步提高哈希值的均匀性。

典型回答 ​

扩展知识 ​

为什么选择base62 ​

MurmurHash的原理 ​

典型回答

扩展知识

为什么选择base62

MurmurHash的原理