哈希算法题目：设计文件系统

题目描述
设计一个内存文件系统，支持以下操作：

1. createPath(path, value) - 创建新路径并赋值
   • 路径格式：/leet/code
   • 要求父路径必须存在（如创建/leet/code前必须存在/leet）
   • 成功返回true，失败返回false
2. get(path) - 获取路径对应的值
   • 路径存在则返回对应值，否则返回-1

解题过程

步骤1：分析数据结构需求

• 需要快速根据路径查找对应值 → 哈希表存储路径到值的映射
• 需要验证路径的父目录是否存在 → 需要检查路径的各级父目录
• 路径采用标准Unix风格，可用/分割处理

步骤2：设计核心数据结构

class FileSystem:
    def __init__(self):
        # 存储路径到值的映射
        self.path_map = {}
        # 初始化根目录
        self.path_map[""] = 0  # 空字符串代表根目录

步骤3：实现createPath方法
关键点：逐级验证父路径是否存在

def createPath(self, path: str, value: int) -> bool:
    # 路径已存在则失败
    if path in self.path_map:
        return False
    
    # 分割路径获取父目录
    last_slash = path.rfind('/')
    parent_path = path[:last_slash] if last_slash > 0 else ""
    
    # 检查父目录是否存在
    if parent_path not in self.path_map:
        return False
    
    # 创建新路径
    self.path_map[path] = value
    return True

步骤4：实现get方法

def get(self, path: str) -> int:
    return self.path_map.get(path, -1)

步骤5：完整代码实现

class FileSystem:
    def __init__(self):
        self.path_map = {"" : 0}  # 根目录
    
    def createPath(self, path: str, value: int) -> bool:
        if path in self.path_map or not path:
            return False
        
        # 获取父路径
        parent = path[:path.rfind('/')]
        
        # 验证父路径存在（根目录总是存在）
        if parent and parent not in self.path_map:
            return False
        
        self.path_map[path] = value
        return True
    
    def get(self, path: str) -> int:
        return self.path_map.get(path, -1)

步骤6：测试用例验证

# 测试示例
fs = FileSystem()
print(fs.createPath("/leet", 1))     # True
print(fs.createPath("/leet/code", 2)) # True  
print(fs.get("/leet/code"))          # 2
print(fs.createPath("/c/d", 3))      # False（父目录/c不存在）
print(fs.get("/c"))                  # -1

关键要点总结

1. 哈希表选择：使用字典存储路径-值映射，实现O(1)时间复杂度的查找
2. 路径处理：通过rfind('/')高效分割路径和父目录
3. 边界处理：根目录用空字符串表示，确保所有绝对路径都有父目录
4. 错误处理：严格验证路径存在性和父目录依赖关系

这种方法确保了文件系统的基本功能，同时通过哈希表保证了操作的高效性。