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

一、题目描述

你需要设计一个简化版的内存文件系统，支持以下操作：

1. createPath(path, value)

   • 创建一条新路径，并将一个整数值与之关联。
   • 如果路径已经存在，或者父路径不存在，则操作失败，返回 false。
   • 如果创建成功，返回 true。

2. get(path)

   • 返回与路径关联的值。
   • 如果路径不存在，返回 -1。

说明：

• 路径格式为："/a/b/c"，即以斜杠 / 开头，由小写英文字母和斜杠组成。
• 一个路径的父路径是指该路径去掉最后一级目录后的部分。例如，"/a/b/c" 的父路径是 "/a/b"，"/a" 的父路径是 "/"。
• 根路径 "/" 需要在系统初始化时自动存在（不需要显式创建）。
• 路径对应的值均为正整数。

二、解题思路分析

这是一个典型的树形结构+哈希表的复合设计题：

• 文件系统本质是树状目录结构，每个节点（目录/文件）对应一个路径。
• 我们可以用哈希表存储 路径 → 节点信息 的映射，实现 O(1) 的路径查找。
• 创建路径时需要检查父路径是否存在，这可以通过在哈希表中查找父路径来实现。

三、详细设计步骤

步骤1：数据结构设计

我们需要一个哈希表（字典/映射）来存储路径和对应的值：

class FileSystem:
    def __init__(self):
        self.path_map = {"/": None}  # 初始化根路径，值可设为任意值（题目不要求获取根路径的值）

这里我们将根路径 "/" 预先放入哈希表，但注意题目并未要求对根路径调用 get()，所以值可以设为 None 或其他占位符。

步骤2：createPath 实现逻辑

1. 检查路径是否已存在 → 存在则返回 false。
2. 提取父路径：
   • 例如 "/a/b/c" 的父路径是 "/a/b"。
   • 注意处理根路径："/a" 的父路径是 "/"。
3. 检查父路径是否存在 → 不存在则返回 false。
4. 将新路径和对应的值存入哈希表。
5. 返回 true。

边界情况：

• 路径以 / 开头，且不以 / 结尾（除非是根路径）。
• 路径中可能存在多个连续的 / 吗？题目说明路径格式规范，假设输入合法。

步骤3：get 实现逻辑

1. 在哈希表中查找路径。
2. 如果存在，返回值；否则返回 -1。

四、代码实现与逐行解释

class FileSystem:
    def __init__(self):
        # 初始化哈希表，创建根目录
        self.map = {"/": -1}  # 根路径的值用 -1 占位，实际上不会调用 get("/")
    
    def createPath(self, path: str, value: int) -> bool:
        # 1. 如果路径已存在，失败
        if path in self.map:
            return False
        
        # 2. 提取父路径
        # 找到最后一个 '/' 的位置
        last_slash = path.rfind('/')
        parent = path[:last_slash] if last_slash > 0 else "/"
        
        # 3. 如果父路径不存在（除了根路径），失败
        if parent not in self.map:
            return False
        
        # 4. 创建路径
        self.map[path] = value
        return True
    
    def get(self, path: str) -> int:
        # 如果路径存在，返回值；否则返回 -1
        return self.map.get(path, -1)

五、示例演示

假设操作序列如下：

fs = FileSystem()
print(fs.createPath("/a", 1))   # True
print(fs.createPath("/a/b", 2)) # True
print(fs.get("/a/b"))          # 2
print(fs.createPath("/c/d", 3)) # False，因为父路径 "/c" 不存在
print(fs.get("/c"))             # -1

执行过程：

1. 初始化：map = {"/": -1}
2. createPath("/a", 1)：
   • 路径 /a 不在 map 中。
   • 父路径是 "/"，在 map 中。
   • 插入 map["/a"] = 1，返回 true。
3. createPath("/a/b", 2)：
   • 路径 /a/b 不在 map 中。
   • 父路径是 "/a"，在 map 中。
   • 插入 map["/a/b"] = 2，返回 true。
4. get("/a/b") 返回 2。
5. createPath("/c/d", 3)：
   • 父路径 "/c" 不在 map 中 → 返回 false。
6. get("/c") 返回 -1。

六、复杂度分析

• createPath：
  • 提取父路径需要 O(L) 时间（L 为路径长度），哈希表查找 O(1)。
  • 总时间复杂度 O(L)，空间复杂度 O(N*L)，N 为路径数量。
• get：
  • 哈希表查找 O(1)。

七、扩展思考

1. 如果要支持删除路径，该如何设计？

   • 需要确保被删除的路径没有子路径，否则应先删除所有子路径。
   • 可维护一个反向映射：父路径 → 子路径集合，用于快速判断。

2. 如果路径数量极大，如何优化内存？

   • 使用前缀树（Trie）存储路径，共享公共前缀，节省空间。

3. 如果系统需要支持列出某个路径下的所有子路径？

   • 在节点中维护子节点列表，或使用哈希表存储父路径到子路径集合的映射。

八、总结

本题通过哈希表实现了快速路径查找和父路径验证，核心在于：

• 利用哈希表 O(1) 查询的特性。
• 正确处理路径字符串，提取父路径。
• 注意边界条件（根路径、路径格式）。

这个设计是实际文件系统、配置管理、路由表等应用的简化原型，体现了哈希表在快速键值存取中的关键作用。