好的，我们来探讨一个你列表中尚未出现过、且非常经典的哈希算法应用问题。

哈希算法题目：字符串的编码与解码（TinyURL的增强版）

题目描述

设计一个算法来将一个长URL编码成一个短的URL，同时也能将短的URL解码回原始的长URL。此外，系统需要支持一个自定义短码的功能，即用户可以为自己的长URL指定一个期望的短字符串作为后缀。

具体要求：

1. String encode(String longUrl): 将一个长URL编码为一个短URL。短URL的格式为 "http://tinyurl.com/" + <短码>。如果用户没有指定自定义短码，则系统需要自动生成一个唯一的、难以预测的短码。
2. String encode(String longUrl, String customShortCode): 将长URL编码为指定短码的短URL。如果该短码已经被占用，则编码失败，返回一个错误提示（例如 "custom code already in use"）。
3. String decode(String shortUrl): 将短URL解码回原始的长URL。如果短码不存在，则返回错误提示（例如 "short url not found"）。

核心挑战：

• 唯一性： 如何保证自动生成的短码全局唯一且不重复？
• 安全性/不可预测性： 自动生成的短码不应是简单的递增数字，以防被他人轻易遍历。
• 冲突处理： 如何处理自定义短码与已有短码的冲突？
• 效率： 编码（尤其是自动生成）和解码操作需要在常数时间 O(1) 内完成。

解题过程循序渐进讲解

这个问题本质上是设计一个双向的、支持自定义键的键值对存储系统。哈希表是解决此类问题的核心数据结构。

步骤一：确定核心数据结构

我们需要建立两种映射关系：

1. 长URL -> 短码： 用于在用户重复提交相同长URL时，可以直接返回已有的短码，避免重复存储，也支持自定义短码时的冲突检查。
2. 短码 -> 长URL： 这是核心的解码映射。给定短码，必须能立刻找到其对应的长URL。

因此，我们使用两个哈希表（字典）：

• longToShort: Map<String, String>: 键为长URL，值为短码。
• shortToLong: Map<String, String>: 键为短码，值为长URL。

// 伪代码初始化
Map<String, String> longToShort = new HashMap<>();
Map<String, String> shortToLong = new HashMap<>();

步骤二：设计自动生成唯一短码的算法

这是本题的关键技术点。我们不能使用简单的自增ID（如1, 2, 3...），因为这样生成的短码 "http://tinyurl.com/1" 非常容易被猜到，导致系统被恶意遍历。

一个经典且高效的方案是使用哈希函数 + 重试机制。

1. 选择一个哈希函数： 我们使用 MD5 或 SHA-256 等加密哈希函数。它们具有“雪崩效应”，输入（长URL）的微小变化会导致输出（哈希值）的巨大差异，且结果近乎随机，难以预测。
2. 将哈希值转换为短码： 哈希函数输出是一串很长的十六进制数（如128位或256位）。我们可以截取前 N 位（例如6位或8位）作为短码。但这引入了哈希冲突的可能：两个不同的长URL可能产生相同的前N位哈希值。
3. 解决冲突： 当我们为一个长URL自动生成短码时：
   a. 先计算其哈希值（例如MD5），取前6个字符。
   b. 检查 shortToLong 映射中这个短码是否已被占用。
   c. 如果未被占用，则建立映射，返回这个短码。✅
   d. 如果已被占用，说明发生了冲突。我们需要重新生成一个短码。一个常见的策略是在原长URL上追加一个随机盐（salt）或递增的计数器，然后重新计算哈希，直到找到一个未被占用的短码为止。

// 自动生成短码的伪代码示例
String generateShortCode(String longUrl) {
    int retryCount = 0;
    String salt = "";
    while (true) {
        // 计算 longUrl + salt 的哈希，并取前6位
        String hash = calculateMD5(longUrl + salt).substring(0, 6);
        if (!shortToLong.containsKey(hash)) {
            return hash; // 找到唯一短码
        }
        // 发生冲突，改变输入重新尝试
        retryCount++;
        salt = String.valueOf(retryCount); // 使用递增数字作为盐
        // 理论上，在短码空间（62^6种可能）耗尽前总能找到，概率极低
    }
}

步骤三：实现 encode(String longUrl) （自动编码）

1. 查重： 首先检查 longToShort 表，如果这个长URL已经存在对应的短码，直接返回已经生成的短URL。
2. 生成： 如果不存在，调用 generateShortCode(longUrl) 函数生成一个唯一的短码。
3. 存储： 在 longToShort 和 shortToLong 两个表中分别建立 longUrl -> shortCode 和 shortCode -> longUrl 的映射。
4. 返回： 拼接基础域名和短码，返回完整的短URL。

String baseUrl = "http://tinyurl.com/";

String encode(String longUrl) {
    // 1. 检查是否已编码过
    if (longToShort.containsKey(longUrl)) {
        return baseUrl + longToShort.get(longUrl);
    }
    // 2. 生成唯一短码
    String shortCode = generateShortCode(longUrl);
    // 3. 存储双向映射
    longToShort.put(longUrl, shortCode);
    shortToLong.put(shortCode, longUrl);
    // 4. 返回结果
    return baseUrl + shortCode;
}

步骤四：实现 encode(String longUrl, String customShortCode) （自定义编码）

1. 冲突检查： 首先检查 shortToLong 表，看期望的 customShortCode 是否已经被其他长URL占用。
2. 失败处理： 如果已被占用，立即返回错误信息。
3. 存储： 如果未被占用：
   a. 在 shortToLong 中建立 customShortCode -> longUrl 映射。
   b. 在 longToShort 中建立 longUrl -> customShortCode 映射（注意，如果这个长URL之前有自动生成的短码，这里会被覆盖，自动生成的旧映射失效）。
4. 返回： 返回拼接好的短URL。

String encode(String longUrl, String customShortCode) {
    // 1. 检查自定义短码是否已存在
    if (shortToLong.containsKey(customShortCode)) {
        // 2. 如果存在，需要检查它映射的是否是当前这个长URL
        // 如果是同一个长URL，可以视为成功（幂等操作）或返回已存在
        // 通常我们认为自定义短码唯一，直接返回错误
        return "Error: custom code already in use";
    }
    // 3. 存储新映射
    // 先移除长URL可能存在的旧映射（如果之前自动生成过）
    if (longToShort.containsKey(longUrl)) {
        String oldCode = longToShort.get(longUrl);
        shortToLong.remove(oldCode); // 使旧的自动短码失效
    }
    shortToLong.put(customShortCode, longUrl);
    longToShort.put(longUrl, customShortCode);
    // 4. 返回结果
    return baseUrl + customShortCode;
}

步骤五：实现 decode(String shortUrl)

1. 提取短码： 从完整的短URL（如 "http://tinyurl.com/abc123"）中提取出短码部分（"abc123"）。
2. 查找： 在 shortToLong 哈希表中用短码作为键进行查找。
3. 返回：
   • 如果找到，返回对应的长URL。
   • 如果未找到，返回错误信息。

String decode(String shortUrl) {
    // 1. 提取短码。简单处理，从最后一个'/'之后开始截取
    String shortCode = shortUrl.substring(shortUrl.lastIndexOf('/') + 1);
    // 2. 在映射中查找
    if (shortToLong.containsKey(shortCode)) {
        return shortToLong.get(shortCode);
    } else {
        return "Error: short url not found";
    }
}

步骤六：总结与复杂度分析

• 时间复杂度：
  • encode (自动)：平均 O(1)。哈希计算是常数时间，虽然可能有冲突重试，但在良好的哈希函数和足够短码长度下，冲突概率极低，平均重试次数可视为常数。
  • encode (自定义)：O(1)。主要是两次哈希表查找和插入。
  • decode：O(1)。一次哈希表查找。
• 空间复杂度： O(N)，其中 N 是存储的唯一长URL的数量。我们需要在两个哈希表中为每个长URL保存一条记录。
• 优点：
  1. 自动生成的短码具有随机性，难以被遍历猜测。
  2. 双向映射保证了编码和解码的高效性和唯一性。
  3. 支持自定义短码，功能更加灵活。

最终方案的核心思想就是：利用加密哈希函数生成随机、唯一的标识符，并用哈希表来管理短码与长URL之间的双向映射关系，从而实现高效、可靠的编解码服务。 像现实中的 TinyURL、Bitly 等服务，其后台核心原理与此类似。