字符串的编码与解码（TinyURL的增强版）

题目描述
设计一个算法来对URL（统一资源定位符）字符串进行编码与解码。这个系统类似于TinyURL，但需要增强功能：支持自定义短码（可选），并且需要处理大规模URL时保持高性能与低冲突。要求编码后的字符串尽可能短，且能够唯一地解码回原始URL。

解题过程循序渐进讲解

步骤1：理解核心需求
我们需要实现两个核心函数：

• encode(longUrl: str) -> str: 将长URL编码成一个短字符串（短码）。
• decode(shortUrl: str) -> str: 将短码解码回原始长URL。

关键点：

1. 同一个长URL每次编码应得到同一个短码（幂等性）。
2. 不同的长URL应尽可能得到不同的短码（避免冲突）。
3. 短码要尽可能短，以节省空间。
4. 解码必须准确无误。

步骤2：基础方案——使用自增ID与哈希映射
最简单的思路是使用一个自增数字ID作为短码，并用两个哈希表（或字典）存储映射关系：

• id_to_url: 键是数字ID，值是长URL，用于解码。
• url_to_id: 键是长URL，值是数字ID，用于避免重复编码同一URL。

编码过程：

1. 检查长URL是否已经在url_to_id中：
   • 如果在，直接返回基础短域名（如 "http://short.com/"）拼接该ID。
   • 如果不在，分配一个新的ID（从1开始自增），将(ID, 长URL)存入id_to_url，将(长URL, ID)存入url_to_id，然后返回短域名拼接该ID。

解码过程：

1. 从短URL中提取出ID部分（例如从"http://short.com/5"提取出"5"）。
2. 在id_to_url中用这个ID作为键查找，返回对应的长URL。

优点：实现简单，保证唯一性，解码快速。
缺点：短码是连续数字，容易被猜测，且随着ID增大，短码会变长（虽然可以通过进制转换缩短，例如用62进制表示数字）。

步骤3：增强功能1——使用哈希函数生成短码
为了生成更不可预测的短码，我们可以用哈希函数（如MD5、SHA-1、CRC32等）对长URL计算哈希值，然后取哈希值的前若干位（例如6个字符）作为短码。但需要处理哈希冲突。

具体方案：

1. 计算长URL的哈希值（例如用MD5得到128位，或SHA-1得到160位）。
2. 将哈希值转换为Base62字符串（包含数字0-9、小写字母a-z、大写字母A-Z），取前6个字符作为短码。
3. 检查这个短码是否已经被使用：
   • 如果没有被使用，将(短码, 长URL)存入哈希表code_to_url，并返回短域名拼接短码。
   • 如果已经被使用（冲突发生），则用哈希值加上一个随机数或采用二次哈希重新计算，直到找到一个未使用的短码。

编码示例：

• 长URL: "https://example.com/very/long/url"。
• 计算MD5哈希（16进制）: "5d41402abc4b2a76b9719d911017c592"。
• 转换为Base62并取前6位: 假设得到 "aBcDeF"。
• 短URL: "http://short.com/aBcDeF"。

解码：直接从code_to_url中通过短码查找长URL。

优点：短码不可预测，长度固定（例如6字符）。
缺点：仍可能发生哈希冲突（虽然概率很低），需要冲突解决机制。

步骤4：增强功能2——支持自定义短码
允许用户指定自定义短码（例如 "short.com/myPage"），需要检查该短码是否已被占用。

实现：

• 在encode函数中增加一个可选参数custom_code。
• 如果提供了custom_code，检查它是否已在code_to_url中存在：
  • 如果不存在，则使用这个自定义短码建立映射。
  • 如果已存在且对应的长URL不同，则拒绝请求（或返回错误）。
  • 如果已存在且对应相同长URL，可直接返回（幂等性）。
• 如果没有提供custom_code，则按步骤3自动生成短码。

步骤5：系统设计与优化
在实际大规模系统中，还需考虑：

1. 持久化存储：哈希表应存储在数据库（如Redis或SQL）中，以便服务重启后数据不丢失。
2. 分布式系统：可以使用分布式键值存储（如Redis集群）来存储映射，并采用一致性哈希来分摊负载。
3. 短码字符集：使用Base62（62个字符）可让6位短码表示 62^6 ≈ 568亿个URL，基本够用。若需要更多，可增加长度到7或8位。
4. 性能：编码和解码都是O(1)哈希表操作，非常快。但哈希计算（如MD5）有固定开销，仍可接受。
5. 清理过期URL：可增加TTL（生存时间）机制，定期清理久未访问的短URL，回收短码。

步骤6：最终方案伪代码

import hashlib
import base64

class Codec:
    def __init__(self):
        self.prefix = "http://short.com/"
        self.code_to_url = {}  # 短码 -> 长URL
        self.url_to_code = {}  # 长URL -> 短码（用于幂等性）
        
    def encode(self, longUrl, custom_code=None):
        if longUrl in self.url_to_code:
            return self.prefix + self.url_to_code[longUrl]
        
        if custom_code is not None:
            if custom_code in self.code_to_url:
                if self.code_to_url[custom_code] != longUrl:
                    raise Exception("Custom code already in use.")
                else:
                    return self.prefix + custom_code
            short_code = custom_code
        else:
            # 自动生成短码
            short_code = self._hash_url(longUrl)
            # 处理冲突
            while short_code in self.code_to_url:
                # 在原始长URL后加一个随机字符串再哈希，或使用二次哈希
                longUrl += "#"  # 简单示例，实际可用更复杂的盐值
                short_code = self._hash_url(longUrl)
        
        self.code_to_url[short_code] = longUrl
        self.url_to_code[longUrl] = short_code
        return self.prefix + short_code
    
    def decode(self, shortUrl):
        code = shortUrl.replace(self.prefix, "")
        return self.code_to_url.get(code, "")
    
    def _hash_url(self, url):
        # 计算MD5哈希，取前6个Base62字符
        md5 = hashlib.md5(url.encode()).digest()
        # 将16字节MD5转换为Base64（URL安全），然后替换非字母数字字符
        b64 = base64.urlsafe_b64encode(md5).decode().rstrip("=")
        # 只取字母和数字（模拟Base62），这里简化处理：移除非字母数字字符
        b62 = ''.join(c for c in b64 if c.isalnum())
        return b62[:6]  # 返回前6位作为短码

测试示例：

codec = Codec()
url = "https://example.com/very/long/url"
short = codec.encode(url)  # 例如 "http://short.com/aBcDeF"
original = codec.decode(short)  # 应返回原始长URL

总结
本题目结合了哈希表映射、哈希函数、冲突解决和系统设计思想。核心是利用哈希表实现O(1)的编码与解码，并通过哈希函数生成紧凑短码。增强功能包括自定义短码和冲突处理，适合大规模URL缩短服务。