哈希算法题目：设计一个基于哈希的短网址系统

题目描述
设计一个短网址系统，将长URL转换为短URL（如 https://short.url/abc123）。系统需支持：

1. encode(longUrl)：将长URL转换为短URL。
2. decode(shortUrl)：将短URL还原为长URL。
3. 短URL需唯一且尽可能短，能处理大量URL的映射关系。

解题过程

步骤1：理解核心需求

• 长URL到短URL的映射需一一对应，且支持双向查找。
• 短URL路径（如 abc123）需足够短（通常6-8字符），且需避免重复。
• 系统需高效处理高并发请求，考虑哈希冲突和存储扩展性。

步骤2：设计短URL生成方案
常用方法：

1. 哈希函数（如MD5、SHA-1） + 编码（Base62）

   • 对长URL计算哈希值，取前若干位（如6字节）转换为Base62编码（0-9, a-z, A-Z），生成短字符串。
   • 优点：哈希分布均匀，长度固定。
   • 挑战：需处理哈希冲突（不同长URL可能生成相同短URL）。

2. 自增ID + Base62编码

   • 为每个长URL分配唯一自增ID，将ID转换为Base62字符串。
   • 优点：无冲突，短URL长度随ID增长。
   • 挑战：需维护全局ID计数器，分布式环境下需保证ID唯一性。

本题选择哈希函数+Base62方案，重点解决冲突处理。

步骤3：数据结构设计

• 使用两个哈希表（字典）实现双向映射：
  • long_to_short：键为长URL，值为短URL。
  • short_to_long：键为短URL，值为长URL。
• 目的：
  • encode时先查 long_to_short，避免重复生成。
  • decode时直接查 short_to_long，实现O(1)查找。

步骤4：生成短URL的详细流程

1. 输入长URL，检查是否已存在映射：
   • 若 long_to_short 中存在，直接返回对应短URL。
2. 若不存在，生成短URL：
   • 计算哈希值：使用MD5或CRC32等算法（本题用MD5示例）。

     import hashlib  
     hash_hex = hashlib.md5(longUrl.encode()).hexdigest()  # 32字节十六进制字符串  
     

   • 取前6字节（12位十六进制数），转换为整数：

     hash_int = int(hash_hex[:12], 16)  # 0~2^48-1 范围的整数  
     

   • Base62编码：将整数转换为62进制字符串（0-9, a-z, A-Z）：

     chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"  
     short_key = ""  
     while hash_int > 0:  
         short_key = chars[hash_int % 62] + short_key  
         hash_int //= 62  
     

     若结果不足6字符，左侧补'0'至6位（本例中6字节哈希整数通常生成6-7字符）。
3. 处理冲突：
   • 检查 short_to_long 是否已存在该短URL：
     • 若不存在，直接建立映射。
     • 若存在且对应长URL相同（理论上不可能），直接返回。
     • 若存在且长URL不同（哈希冲突），追加后缀（如添加随机字符）重新哈希，直到生成唯一短URL。

步骤5：完整代码实现（Python示例）

import hashlib  

class Codec:  
    def __init__(self):  
        self.long_to_short = {}  
        self.short_to_long = {}  
        self.base62_chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"  

    def encode(self, longUrl: str) -> str:  
        # 已存在映射则直接返回  
        if longUrl in self.long_to_short:  
            return self.long_to_short[longUrl]  

        # 生成短URL键  
        short_key = self._generate_short_key(longUrl)  
        base_url = "https://short.url/"  
        short_url = base_url + short_key  

        # 保存映射  
        self.long_to_short[longUrl] = short_url  
        self.short_to_long[short_url] = longUrl  
        return short_url  

    def decode(self, shortUrl: str) -> str:  
        return self.short_to_long.get(shortUrl, "")  

    def _generate_short_key(self, longUrl: str, retry=0) -> str:  
        # 计算MD5哈希  
        hash_hex = hashlib.md5((longUrl + str(retry)).encode()).hexdigest()  
        hash_int = int(hash_hex[:12], 16)  # 取前12位十六进制数  

        # Base62编码  
        key = ""  
        n = hash_int  
        for _ in range(6):  # 固定生成6字符  
            n, r = divmod(n, 62)  
            key = self.base62_chars[r] + key  
            if n == 0:  
                break  
        key = key.zfill(6)  # 不足6位左侧补0  

        # 冲突处理  
        short_url = "https://short.url/" + key  
        if short_url not in self.short_to_long:  
            return key  
        else:  
            # 递归重试，添加后缀避免无限循环  
            return self._generate_short_key(longUrl, retry + 1)  

步骤6：关键点分析

1. 哈希冲突概率：
   • 6字符Base62编码空间为 \(62^6 \approx 568\) 亿，冲突概率低（生日悖论下仍需千万级URL才需关注）。
2. 效率优化：
   • 双向哈希表保证O(1)的编码和解码时间。
   • 冲突处理通过递归重试，实际中可限制重试次数。
3. 扩展性：
   • 分布式环境下可用全局发号器（如雪花算法）替代哈希方案，避免冲突。
   • 短URL可进一步压缩长度（如用更短字符集）。

通过以上步骤，我们实现了基于哈希的短网址系统，兼顾唯一性、效率和可扩展性。