Day_10任务是把方向Direction用字典装起来key 是字符串。这句话听起来简单真正动手时却牵扯出不少值得掰扯的东西。我在一个练手项目里做网格地图移动角色要通过指令移动最直观的做法就是准备一张“方向表”字符串up对应向上走一步字符串down对应向下走一步。这个东西本质就是一个 key 为字符串的字典。往小说是几行代码往大了说它是理解哈希表、字符串散列、冲突处理的最佳入口。这篇记录下来适合刚学完字典语法、想往数据结构底层看一眼的同学也适合做游戏 Demo 时需要快速实现方向映射的朋友。1. 为什么我在第10天选了这个需求1.1 从游戏Demo里的方向表说起在方格地图上角色移动是最常见的需求。我当时的做法简单粗暴用四个 if 判断字符串然后改变 x、y。比如if direction up: y - 1。写了四个分支后我意识到这不仅仅是动作重复的问题后续如果要加斜向移动、转身动画、技能朝向if 会越堆越多。所以把方向映射成一张字典是更聪明的方式。direction 是字符串值可以是个二元组(dx, dy)也可以是个更复杂的对象。对比 if 链字典的查找复杂度是 O(1)并且把数据和逻辑分离新增方向只需要改字典不用动判断逻辑。这个需求虽然小但它是很多系统设计的基础。1.2 字符串作key和枚举作key的取舍有人会问既然方向固定四个为什么不用枚举或整数做 key这确实是个好问题。用枚举更安全、编译期能检查、性能还更好游戏客户端里很多团队会这么干。但我在这个练手项目里刻意选择了字符串 key原因有两个第一方向的输入来自外部文本指令比如聊天框输入、配置文件读取、网络消息它们天然是字符串如果用枚举还需要多做一层字符串到枚举的转换第二字符串 key 的字典可读性好打印出来一眼能看出up对应什么调试方便。当然如果是在性能极度敏感、每秒调用百万次的热路径上或者你希望编译器帮你检查拼写错误那应该用枚举或整数 key。字符串 key 的字典并不是银弹它适合“外部输入不可控、需要动态映射”的场景。1.3 搞清楚你要“用字典”还是“造字典”实现这个需求时可以走两条路一是直接用语言内置的 dict或 map、Dictionary来存储映射这是绝大多数生产环境推荐的方式二是从零手写一个只支持字符串 key 的字典用哈希表实现目的是搞懂底层原理。Day_10 我当时两个都做了。先用内置 dict 快速跑通业务后来又花时间手写了一遍因为我发现“key 是字符串”这个限定词暴露了哈希表的核心字符串必须被转成哈希值然后决定存到哪个桶里。如果你能把手写的字符串字典做出来你对内置 dict 的很多“魔法”就不再困惑。两条路线不冲突做下来收获很不一样。2. 语言内置字典的实现与使用细节2.1 Direction映射的标准写法先说说最直接、能跑通的写法。用 Python 演示最直观DIRECTIONS { up: (0, -1), down: (0, 1), left: (-1, 0), right: (1, 0), }这个字典的 key 是字符串value 是坐标偏移量。使用时dx, dy DIRECTIONS[command] x dx y dy如果担心 command 不在表里用DIRECTIONS.get(command, (0, 0))或先判断。这里(0, 0)表示原地不动也可以抛异常。类似的写法在 JavaScript 里是对象或MapJava 是HashMapString, int[]C# 是Dictionarystring, Vector2Int。不同语言语法不同但核心思路一致用字符串做键把方向名映射到行为数据。2.2 小心字符串key的坑拼写、大小写、默认值字符串 key 最大的坑就是“看起来一样实际不一样”。比如up和Up是两个不同的 key在 Python 里区分大小写配置文件中如果多了一个空格比如up 也会查不到。我实测下来最稳妥的做法是在数据入口统一做规范化比如command command.strip().lower()然后再查字典。另外不要把默认值设成(0, 0)就以为万事大吉如果移动逻辑里没有检查返回值遇到未知方向就可能原地踏步但用户以为卡了。更好的方式是在 Debug 模式下直接抛异常快速暴露问题dx, dy DIRECTIONS[command]这行代码遇到不存在的 key 会抛KeyError反而好排查。如果用了.get(command, (0, 0))错误会被掩盖。我在调试时一般靠异常抓问题上线前再补一层用户提示。2.3 遍历顺序与稳定性问题另一个容易被忽略的是字典的遍历顺序。Python 3.7 的 dict 会保持插入顺序Java 的 HashMap 不保证顺序JavaScript 的普通对象对整数类型 key 还会自动排序。如果方向表本身不关心顺序那无所谓但如果你要按固定顺序渲染菜单或输出配置千万别依赖字典内部顺序。一个更稳的方案是单独维护一个方向列表比如[up, down, left, right]用列表控制展示顺序用字典做快速查询。这就是“数据存储”和“业务顺序”分离的思路。其实这点也适用于任何以字符串为 key 的映射写成代码要尽量显式不要依赖哈希表的底层实现细节。2.4 字典序列化与配置加载的坑当方向字典需要保存到配置文件或从 JSON 加载时另一个坑出现了JSON 对象的 key 也必须是字符串这一点正好匹配字符串 key 字典但 value 里的元组序列化后会变成数组加载后要转回元组。我有一个习惯在代码里维护一个明确的转换函数不依赖隐式转换。比如import json def load_directions(json_path): with open(json_path, r, encodingutf-8) as f: raw json.load(f) return {k: tuple(v) for k, v in raw.items()}这个函数把数组转成 tuple确保后续使用时不会因为“列表和元组不可哈希”之类的问题踩坑。其实这更像是在提醒自己字典的 key 是字符串但 value 的类型也要在边界处做校验。如果加载出来的是[0, -1]而代码里期望元组解包时虽然能成功但类型不严谨容易埋雷。3. 手写一个字符串key字典哈希表实现3.1 为什么值得手写内置 dict 已经很好用了但“key 为字符串的字典”这个需求用手写一遍会打开新世界。内置 dict 的底层是哈希表它需要解决两件事一是把任意字符串计算成一个整数哈希值二是把哈希值映射到数组下标同时处理多个字符串得到同一个下标的情况。我在手写之前一直以为“字典就是一个无限大的抽屉柜”其实它是一个“有限大小的桶数组哈希函数”的组合。理解这张图后很多问题比如为什么 key 必须是不可变的、为什么扩容会影响性能、为什么字典查找是 O(1) 平均都迎刃而解。3.2 哈希函数与字符串散列字符串哈希有很多种最经典的是一个循环从 0 开始每次乘一个质数比如 31再加上字符的 Unicode 码。这也是 Java 的String.hashCode采用的做法简单且分布相对均匀。Python 里可以这么写def hash_string(s: str) - int: h 0 for ch in s: h h * 31 ord(ch) return h这个值可能很大我们需要把它映射到桶数组的范围内。常规做法是取模index hash_string(key) % bucket_count。但这里有个隐藏问题如果桶数量是 2 的幂且哈希值低位的分布不好可能导致大量碰撞。所以在实际哈希表实现里很多语言会先做一次“扰动”让高位也能参与低位计算。手写练习时建议用一个质数作为桶数量可以暂时避开这个难题。3.3 冲突解决链地址法实现步骤两个不同的字符串可能算出相同的桶下标这就是冲突。解决冲突最简单的方法是链地址法每个桶不是一个单独的条目而是一个链表或数组冲突时就追加到同一个桶里。查找时先定位桶再遍历桶内元素逐个比较 key 是否相等。比较 key 必须是全量比较不能用哈希值代替因为哈希值相同不代表字符串相同。这里有个经验之谈为了效率桶内可以存(hash, key, value)三元组先比哈希值再比 key能减少字符串比较开销。不过练手阶段直接比较 key 也完全没问题。手写结构可以这样设计class StringDict: def __init__(self, capacity8): self.capacity capacity self.buckets [[] for _ in range(capacity)] self.size 0 def _index(self, key: str) - int: return hash_string(key) % self.capacity def put(self, key: str, value): idx self._index(key) for i, (k, v) in enumerate(self.buckets[idx]): if k key: self.buckets[idx][i] (k, value) return self.buckets[idx].append((key, value)) self.size 1 def get(self, key: str): idx self._index(key) for k, v in self.buckets[idx]: if k key: return v raise KeyError(key) def __contains__(self, key: str) - bool: idx self._index(key) return any(k key for k, _ in self.buckets[idx])这段代码已经把核心逻辑完整表达了。注意put覆盖已有 key 时需要更新原条目而不是追加新条目否则同一个 key 会出现两次违背字典语义。3.4 负载因子与扩容手写字典时如果容量固定随着插入越来越多桶内链表会越来越长查找慢慢退化成线性扫描。哈希表用“负载因子”来衡量空间占用即size / capacity。一般控制在 0.7 左右比较合适。当负载因子超过阈值就做一次扩容创建一个更大的桶数组把所有旧条目重新计算下标放进去。为什么必须重算下标因为哈希值取模时用到了旧容量新容量下取模结果会变所以不能直接搬迁。这一步看起来简单但实现时最容易漏掉扩容后忘了把旧桶清空或者遍历旧桶时边遍历边修改都会出问题。我第 10 天写扩容时就在“遍历旧数组的同时插入新数组”上卡了一会儿原因是旧数组和新数组在内存里是两块独立的应该先遍历旧的全部再让self.buckets指向新数组顺序不要反过来。扩容后的容量选择也有讲究。最省事的是capacity * 2但如果你用了“容量必须是质数”的约束就得找下一个质数。练手阶段用两倍扩容完全够用后面再考虑更高级的等比扩容。下面是一个示例def _resize(self): old_buckets self.buckets self.capacity * 2 self.buckets [[] for _ in range(self.capacity)] for bucket in old_buckets: for key, value in bucket: idx self._index(key) self.buckets[idx].append((key, value))这里没有重新计算 size因为 put 操作会在外部调用如果通过这个私有方法后再 putsize 仍是旧值。如果要封装成公共方法还需把 size 重置或重新累计。这个细节不复杂但很值得亲手敲一遍。3.5 为什么 key 必须是不可变类型在实现手写字典时我一开始想过用列表做 key结果不行。原因是哈希表依赖“哈希值稳定”如果 key 的内容变了哈希值就要跟着变但表中的存储位置是根据旧哈希值算出来的会导致再也查不到。字符串是不可变的所以适合做 key。自定义类做 key 时也需要保证哈希方法基于不可变字段。这个点看似基础但手写哈希时会更深刻地体会哈希值相当于 key 的“指纹”指纹变了人还是原来的人但档案柜里的位置已经不对了。所以务必要让 key 不可变。用 tuple 做 key 可以list 不行。4. 实战用Direction字典驱动网格移动4.1 定义数据结构与初始化把前面说的内容落地做一个完整方向字典。我当时的场景是 5x5 的网格玩家最初在左上角输入一串方向字符串就能移动。为了方便演示我用内置 dict 作为正式方案同时把手写的 StringDict 作为底层实现接入这样能验证手写字典是否正确。先定义方向表DIRECTIONS { up: (0, -1), down: (0, 1), left: (-1, 0), right: (1, 0), }坐标系的约定是 x 向右、y 向下这样更符合屏幕坐标习惯。如果做数学坐标把 y 的正负反过来就行。我在这里栽过跟头up 到底应不应该让 y 减一取决于坐标系。为了一致性最好画一张坐标图贴在屏幕前至少在当时我把每条方向写在注释里防止自己记反。4.2 核心逻辑根据方向字符串获取位移移动函数很简单def move(pos, command): dx, dy DIRECTIONS[command] x, y pos return (x dx, y dy)但如果要支持边界可以加参数def move(pos, command, width5, height5): dx, dy DIRECTIONS[command] x, y pos nx, ny x dx, y dy if 0 nx width and 0 ny height: return (nx, ny) return pos这样遇到边界会留在原地。实际测试时我连续输入up, left, down, right走一圈能回到起点再输入up时 y 已经到 0系统正确拒绝越界。手写 StringDict 版本就是把DIRECTIONS[command]换成dict_obj.get(command)其余逻辑一模一样。这也能验证手写字典的语义是否与内置一致。4.3 效果测试与边界情况测试时除了正常路径还应该测这些大小写不一致的 key、未知 key、重复移动到底或到右边界、空字符串。我给每个 key 做了 strip 处理确保输入 up 也能被识别。对于未知 key在测试代码里用try...except捕获而不是直接崩溃。调用手写字典时我特意写了几个用例比如put(up, (0, -1))后先get(up)再用新 value 覆盖检查是否更新成功。覆盖逻辑是我觉得最容易写错的地方因为有些初版代码只做追加导致 get 老是返回旧值。我测试时专门验证了覆盖这也是字典语义的核心。4.4 把内置dict替换成手写StringDict的完整实现前面给了 StringDict 的骨架现在把它接进移动 Demo。为了让业务层无感可以做一个适配函数def build_dict_from_stringdict(pairs, capacity8): d StringDict(capacity) for k, v in pairs: d.put(k, v) return d然后移动逻辑里写def move_with_dict(pos, command, table, bounds): if command not in table: return pos, unknown dx, dy table.get(command) x, y pos nx, ny x dx, y dy if 0 nx bounds[0] and 0 ny bounds[1]: return (nx, ny), ok return pos, blocked这个table既可以是内置 dict也可以是 StringDict因为业务层只调用get和__contains__不关心底层实现。这样测试时就能用同一套逻辑对比两种实现。我跑下来的结果完全一致说明手写版本的核心语义是成立的。当然我的 StringDict 还没实现迭代和删除方法作为第 10 天的练习功能上限不需要太高重点是哈希表主路径。5. 常见问题与排查技巧实录5.1 方向字符串接反了坐标系的坑这是我认为最高频的问题。如果你按数学坐标系写up: (0, 1)在屏幕坐标系里等于向下角色会反向移动。排查方法很简单打印当前位置手动算一遍期望值对比实际值。如果方向都反了不是字典的问题是坐标定义的问题。一个小技巧是给每个 value 用注释写上“相对坐标”比如up: (0, -1) # y 减小向上这样之后再回来改代码时不会二义。5.2 字典的key查不到返回nil导致崩溃内置 dict 的dict[key]在 key 不存在时会抛 KeyError。如果你用get返回默认值要小心默认值本身是不是合法的位移。比如get(command, (0, 0))返回(0, 0)会让角色原地不动表面看不出来错误但如果命令来自配置文件可能是个拼写错误。我的习惯是对外部输入先做白名单校验不在白名单里就直接提示“未知方向”对内部逻辑访问字典则使用[]让异常早点暴露。这样可以兼顾健壮性和可调试性。5.3 手写哈希时散列不均匀手写哈希时如果用了很简单的哈希函数比如把所有字符的 Unicode 值加起来那么ab和ba会得到相同结果碰撞概率很高。乘质数的版本能减少这种问题但也不是绝对。如果你想观察碰撞可以在 StringDict 里加一个统计接口返回每个桶的长度。实测下来用 31 做乘数和取模容量 8 的小表四个方向能完美分散到不同桶但再多一些单词就难免有碰撞。这是正常的关键是让每个桶的链表平均长度保持在小规模。5.4 实战速查表把常见问题和解决方式整理成表格症状可能原因处理方式使用dict[key]抛 KeyErrorkey 大小写或空格不一致入口统一strip().lower()或先做白名单校验使用get返回默认值但角色不动默认值(0,0)掩盖错误改成抛异常或返回状态码方向移动反向坐标系 y 轴方向定义反了在 value 旁注释相对方向测试时打印坐标手写字典中覆盖 key 不生效put 只追加没更新遍历桶内元素相同 key 直接替换手写字典查找越来越慢负载因子过高链表过长扩容并重新哈希所有条目遍历输出顺序不稳定依赖哈希表内部顺序业务上单独维护有序 key 列表这张表直接抄走能省不少排查时间。最后说点我的个人体会。第 10 天这个任务让我意识到字符串 key 的字典是一个“看起来简单、做起来有细节”的东西。内置 dict 帮我们封装了哈希、扩容、内存管理但如果你不知道底层发生了什么一旦遇到诡异问题就无从下手。手写一遍 StringDict 最大的收获不是代码量而是对哈希表的直觉哈希函数、取模、冲突、负载因子每一个概念都有了画面感。后面我再去看其他语言的字典实现比如 Java 的 HashMap 在链表过长时为什么要转红黑树就很容易理解了。如果你也在做类似的练手项目我的建议是先用内置 dict 把功能跑通再抽一个下午手写简化版然后把两种实现都接入同一个业务测试里跑一遍。踩过一次扩容的坑比读十遍理论都管用。这次 Day_10 的记录就到这里下一阶段我打算把方向字典扩展成支持多方向、斜向和旋转角度的版本让这个模块真正能用在更复杂的寻路场景里。
Day_10任务是把方向Direction用字典装起来key 是字符串。这句话听起来简单真正动手时却牵扯出不少值得掰扯的东西。我在一个练手项目里做网格地图移动角色要通过指令移动最直观的做法就是准备一张“方向表”字符串up对应向上走一步字符串down对应向下走一步。这个东西本质就是一个 key 为字符串的字典。往小说是几行代码往大了说它是理解哈希表、字符串散列、冲突处理的最佳入口。这篇记录下来适合刚学完字典语法、想往数据结构底层看一眼的同学也适合做游戏 Demo 时需要快速实现方向映射的朋友。1. 为什么我在第10天选了这个需求1.1 从游戏Demo里的方向表说起在方格地图上角色移动是最常见的需求。我当时的做法简单粗暴用四个 if 判断字符串然后改变 x、y。比如if direction up: y - 1。写了四个分支后我意识到这不仅仅是动作重复的问题后续如果要加斜向移动、转身动画、技能朝向if 会越堆越多。所以把方向映射成一张字典是更聪明的方式。direction 是字符串值可以是个二元组(dx, dy)也可以是个更复杂的对象。对比 if 链字典的查找复杂度是 O(1)并且把数据和逻辑分离新增方向只需要改字典不用动判断逻辑。这个需求虽然小但它是很多系统设计的基础。1.2 字符串作key和枚举作key的取舍有人会问既然方向固定四个为什么不用枚举或整数做 key这确实是个好问题。用枚举更安全、编译期能检查、性能还更好游戏客户端里很多团队会这么干。但我在这个练手项目里刻意选择了字符串 key原因有两个第一方向的输入来自外部文本指令比如聊天框输入、配置文件读取、网络消息它们天然是字符串如果用枚举还需要多做一层字符串到枚举的转换第二字符串 key 的字典可读性好打印出来一眼能看出up对应什么调试方便。当然如果是在性能极度敏感、每秒调用百万次的热路径上或者你希望编译器帮你检查拼写错误那应该用枚举或整数 key。字符串 key 的字典并不是银弹它适合“外部输入不可控、需要动态映射”的场景。1.3 搞清楚你要“用字典”还是“造字典”实现这个需求时可以走两条路一是直接用语言内置的 dict或 map、Dictionary来存储映射这是绝大多数生产环境推荐的方式二是从零手写一个只支持字符串 key 的字典用哈希表实现目的是搞懂底层原理。Day_10 我当时两个都做了。先用内置 dict 快速跑通业务后来又花时间手写了一遍因为我发现“key 是字符串”这个限定词暴露了哈希表的核心字符串必须被转成哈希值然后决定存到哪个桶里。如果你能把手写的字符串字典做出来你对内置 dict 的很多“魔法”就不再困惑。两条路线不冲突做下来收获很不一样。2. 语言内置字典的实现与使用细节2.1 Direction映射的标准写法先说说最直接、能跑通的写法。用 Python 演示最直观DIRECTIONS { up: (0, -1), down: (0, 1), left: (-1, 0), right: (1, 0), }这个字典的 key 是字符串value 是坐标偏移量。使用时dx, dy DIRECTIONS[command] x dx y dy如果担心 command 不在表里用DIRECTIONS.get(command, (0, 0))或先判断。这里(0, 0)表示原地不动也可以抛异常。类似的写法在 JavaScript 里是对象或MapJava 是HashMapString, int[]C# 是Dictionarystring, Vector2Int。不同语言语法不同但核心思路一致用字符串做键把方向名映射到行为数据。2.2 小心字符串key的坑拼写、大小写、默认值字符串 key 最大的坑就是“看起来一样实际不一样”。比如up和Up是两个不同的 key在 Python 里区分大小写配置文件中如果多了一个空格比如up 也会查不到。我实测下来最稳妥的做法是在数据入口统一做规范化比如command command.strip().lower()然后再查字典。另外不要把默认值设成(0, 0)就以为万事大吉如果移动逻辑里没有检查返回值遇到未知方向就可能原地踏步但用户以为卡了。更好的方式是在 Debug 模式下直接抛异常快速暴露问题dx, dy DIRECTIONS[command]这行代码遇到不存在的 key 会抛KeyError反而好排查。如果用了.get(command, (0, 0))错误会被掩盖。我在调试时一般靠异常抓问题上线前再补一层用户提示。2.3 遍历顺序与稳定性问题另一个容易被忽略的是字典的遍历顺序。Python 3.7 的 dict 会保持插入顺序Java 的 HashMap 不保证顺序JavaScript 的普通对象对整数类型 key 还会自动排序。如果方向表本身不关心顺序那无所谓但如果你要按固定顺序渲染菜单或输出配置千万别依赖字典内部顺序。一个更稳的方案是单独维护一个方向列表比如[up, down, left, right]用列表控制展示顺序用字典做快速查询。这就是“数据存储”和“业务顺序”分离的思路。其实这点也适用于任何以字符串为 key 的映射写成代码要尽量显式不要依赖哈希表的底层实现细节。2.4 字典序列化与配置加载的坑当方向字典需要保存到配置文件或从 JSON 加载时另一个坑出现了JSON 对象的 key 也必须是字符串这一点正好匹配字符串 key 字典但 value 里的元组序列化后会变成数组加载后要转回元组。我有一个习惯在代码里维护一个明确的转换函数不依赖隐式转换。比如import json def load_directions(json_path): with open(json_path, r, encodingutf-8) as f: raw json.load(f) return {k: tuple(v) for k, v in raw.items()}这个函数把数组转成 tuple确保后续使用时不会因为“列表和元组不可哈希”之类的问题踩坑。其实这更像是在提醒自己字典的 key 是字符串但 value 的类型也要在边界处做校验。如果加载出来的是[0, -1]而代码里期望元组解包时虽然能成功但类型不严谨容易埋雷。3. 手写一个字符串key字典哈希表实现3.1 为什么值得手写内置 dict 已经很好用了但“key 为字符串的字典”这个需求用手写一遍会打开新世界。内置 dict 的底层是哈希表它需要解决两件事一是把任意字符串计算成一个整数哈希值二是把哈希值映射到数组下标同时处理多个字符串得到同一个下标的情况。我在手写之前一直以为“字典就是一个无限大的抽屉柜”其实它是一个“有限大小的桶数组哈希函数”的组合。理解这张图后很多问题比如为什么 key 必须是不可变的、为什么扩容会影响性能、为什么字典查找是 O(1) 平均都迎刃而解。3.2 哈希函数与字符串散列字符串哈希有很多种最经典的是一个循环从 0 开始每次乘一个质数比如 31再加上字符的 Unicode 码。这也是 Java 的String.hashCode采用的做法简单且分布相对均匀。Python 里可以这么写def hash_string(s: str) - int: h 0 for ch in s: h h * 31 ord(ch) return h这个值可能很大我们需要把它映射到桶数组的范围内。常规做法是取模index hash_string(key) % bucket_count。但这里有个隐藏问题如果桶数量是 2 的幂且哈希值低位的分布不好可能导致大量碰撞。所以在实际哈希表实现里很多语言会先做一次“扰动”让高位也能参与低位计算。手写练习时建议用一个质数作为桶数量可以暂时避开这个难题。3.3 冲突解决链地址法实现步骤两个不同的字符串可能算出相同的桶下标这就是冲突。解决冲突最简单的方法是链地址法每个桶不是一个单独的条目而是一个链表或数组冲突时就追加到同一个桶里。查找时先定位桶再遍历桶内元素逐个比较 key 是否相等。比较 key 必须是全量比较不能用哈希值代替因为哈希值相同不代表字符串相同。这里有个经验之谈为了效率桶内可以存(hash, key, value)三元组先比哈希值再比 key能减少字符串比较开销。不过练手阶段直接比较 key 也完全没问题。手写结构可以这样设计class StringDict: def __init__(self, capacity8): self.capacity capacity self.buckets [[] for _ in range(capacity)] self.size 0 def _index(self, key: str) - int: return hash_string(key) % self.capacity def put(self, key: str, value): idx self._index(key) for i, (k, v) in enumerate(self.buckets[idx]): if k key: self.buckets[idx][i] (k, value) return self.buckets[idx].append((key, value)) self.size 1 def get(self, key: str): idx self._index(key) for k, v in self.buckets[idx]: if k key: return v raise KeyError(key) def __contains__(self, key: str) - bool: idx self._index(key) return any(k key for k, _ in self.buckets[idx])这段代码已经把核心逻辑完整表达了。注意put覆盖已有 key 时需要更新原条目而不是追加新条目否则同一个 key 会出现两次违背字典语义。3.4 负载因子与扩容手写字典时如果容量固定随着插入越来越多桶内链表会越来越长查找慢慢退化成线性扫描。哈希表用“负载因子”来衡量空间占用即size / capacity。一般控制在 0.7 左右比较合适。当负载因子超过阈值就做一次扩容创建一个更大的桶数组把所有旧条目重新计算下标放进去。为什么必须重算下标因为哈希值取模时用到了旧容量新容量下取模结果会变所以不能直接搬迁。这一步看起来简单但实现时最容易漏掉扩容后忘了把旧桶清空或者遍历旧桶时边遍历边修改都会出问题。我第 10 天写扩容时就在“遍历旧数组的同时插入新数组”上卡了一会儿原因是旧数组和新数组在内存里是两块独立的应该先遍历旧的全部再让self.buckets指向新数组顺序不要反过来。扩容后的容量选择也有讲究。最省事的是capacity * 2但如果你用了“容量必须是质数”的约束就得找下一个质数。练手阶段用两倍扩容完全够用后面再考虑更高级的等比扩容。下面是一个示例def _resize(self): old_buckets self.buckets self.capacity * 2 self.buckets [[] for _ in range(self.capacity)] for bucket in old_buckets: for key, value in bucket: idx self._index(key) self.buckets[idx].append((key, value))这里没有重新计算 size因为 put 操作会在外部调用如果通过这个私有方法后再 putsize 仍是旧值。如果要封装成公共方法还需把 size 重置或重新累计。这个细节不复杂但很值得亲手敲一遍。3.5 为什么 key 必须是不可变类型在实现手写字典时我一开始想过用列表做 key结果不行。原因是哈希表依赖“哈希值稳定”如果 key 的内容变了哈希值就要跟着变但表中的存储位置是根据旧哈希值算出来的会导致再也查不到。字符串是不可变的所以适合做 key。自定义类做 key 时也需要保证哈希方法基于不可变字段。这个点看似基础但手写哈希时会更深刻地体会哈希值相当于 key 的“指纹”指纹变了人还是原来的人但档案柜里的位置已经不对了。所以务必要让 key 不可变。用 tuple 做 key 可以list 不行。4. 实战用Direction字典驱动网格移动4.1 定义数据结构与初始化把前面说的内容落地做一个完整方向字典。我当时的场景是 5x5 的网格玩家最初在左上角输入一串方向字符串就能移动。为了方便演示我用内置 dict 作为正式方案同时把手写的 StringDict 作为底层实现接入这样能验证手写字典是否正确。先定义方向表DIRECTIONS { up: (0, -1), down: (0, 1), left: (-1, 0), right: (1, 0), }坐标系的约定是 x 向右、y 向下这样更符合屏幕坐标习惯。如果做数学坐标把 y 的正负反过来就行。我在这里栽过跟头up 到底应不应该让 y 减一取决于坐标系。为了一致性最好画一张坐标图贴在屏幕前至少在当时我把每条方向写在注释里防止自己记反。4.2 核心逻辑根据方向字符串获取位移移动函数很简单def move(pos, command): dx, dy DIRECTIONS[command] x, y pos return (x dx, y dy)但如果要支持边界可以加参数def move(pos, command, width5, height5): dx, dy DIRECTIONS[command] x, y pos nx, ny x dx, y dy if 0 nx width and 0 ny height: return (nx, ny) return pos这样遇到边界会留在原地。实际测试时我连续输入up, left, down, right走一圈能回到起点再输入up时 y 已经到 0系统正确拒绝越界。手写 StringDict 版本就是把DIRECTIONS[command]换成dict_obj.get(command)其余逻辑一模一样。这也能验证手写字典的语义是否与内置一致。4.3 效果测试与边界情况测试时除了正常路径还应该测这些大小写不一致的 key、未知 key、重复移动到底或到右边界、空字符串。我给每个 key 做了 strip 处理确保输入 up 也能被识别。对于未知 key在测试代码里用try...except捕获而不是直接崩溃。调用手写字典时我特意写了几个用例比如put(up, (0, -1))后先get(up)再用新 value 覆盖检查是否更新成功。覆盖逻辑是我觉得最容易写错的地方因为有些初版代码只做追加导致 get 老是返回旧值。我测试时专门验证了覆盖这也是字典语义的核心。4.4 把内置dict替换成手写StringDict的完整实现前面给了 StringDict 的骨架现在把它接进移动 Demo。为了让业务层无感可以做一个适配函数def build_dict_from_stringdict(pairs, capacity8): d StringDict(capacity) for k, v in pairs: d.put(k, v) return d然后移动逻辑里写def move_with_dict(pos, command, table, bounds): if command not in table: return pos, unknown dx, dy table.get(command) x, y pos nx, ny x dx, y dy if 0 nx bounds[0] and 0 ny bounds[1]: return (nx, ny), ok return pos, blocked这个table既可以是内置 dict也可以是 StringDict因为业务层只调用get和__contains__不关心底层实现。这样测试时就能用同一套逻辑对比两种实现。我跑下来的结果完全一致说明手写版本的核心语义是成立的。当然我的 StringDict 还没实现迭代和删除方法作为第 10 天的练习功能上限不需要太高重点是哈希表主路径。5. 常见问题与排查技巧实录5.1 方向字符串接反了坐标系的坑这是我认为最高频的问题。如果你按数学坐标系写up: (0, 1)在屏幕坐标系里等于向下角色会反向移动。排查方法很简单打印当前位置手动算一遍期望值对比实际值。如果方向都反了不是字典的问题是坐标定义的问题。一个小技巧是给每个 value 用注释写上“相对坐标”比如up: (0, -1) # y 减小向上这样之后再回来改代码时不会二义。5.2 字典的key查不到返回nil导致崩溃内置 dict 的dict[key]在 key 不存在时会抛 KeyError。如果你用get返回默认值要小心默认值本身是不是合法的位移。比如get(command, (0, 0))返回(0, 0)会让角色原地不动表面看不出来错误但如果命令来自配置文件可能是个拼写错误。我的习惯是对外部输入先做白名单校验不在白名单里就直接提示“未知方向”对内部逻辑访问字典则使用[]让异常早点暴露。这样可以兼顾健壮性和可调试性。5.3 手写哈希时散列不均匀手写哈希时如果用了很简单的哈希函数比如把所有字符的 Unicode 值加起来那么ab和ba会得到相同结果碰撞概率很高。乘质数的版本能减少这种问题但也不是绝对。如果你想观察碰撞可以在 StringDict 里加一个统计接口返回每个桶的长度。实测下来用 31 做乘数和取模容量 8 的小表四个方向能完美分散到不同桶但再多一些单词就难免有碰撞。这是正常的关键是让每个桶的链表平均长度保持在小规模。5.4 实战速查表把常见问题和解决方式整理成表格症状可能原因处理方式使用dict[key]抛 KeyErrorkey 大小写或空格不一致入口统一strip().lower()或先做白名单校验使用get返回默认值但角色不动默认值(0,0)掩盖错误改成抛异常或返回状态码方向移动反向坐标系 y 轴方向定义反了在 value 旁注释相对方向测试时打印坐标手写字典中覆盖 key 不生效put 只追加没更新遍历桶内元素相同 key 直接替换手写字典查找越来越慢负载因子过高链表过长扩容并重新哈希所有条目遍历输出顺序不稳定依赖哈希表内部顺序业务上单独维护有序 key 列表这张表直接抄走能省不少排查时间。最后说点我的个人体会。第 10 天这个任务让我意识到字符串 key 的字典是一个“看起来简单、做起来有细节”的东西。内置 dict 帮我们封装了哈希、扩容、内存管理但如果你不知道底层发生了什么一旦遇到诡异问题就无从下手。手写一遍 StringDict 最大的收获不是代码量而是对哈希表的直觉哈希函数、取模、冲突、负载因子每一个概念都有了画面感。后面我再去看其他语言的字典实现比如 Java 的 HashMap 在链表过长时为什么要转红黑树就很容易理解了。如果你也在做类似的练手项目我的建议是先用内置 dict 把功能跑通再抽一个下午手写简化版然后把两种实现都接入同一个业务测试里跑一遍。踩过一次扩容的坑比读十遍理论都管用。这次 Day_10 的记录就到这里下一阶段我打算把方向字典扩展成支持多方向、斜向和旋转角度的版本让这个模块真正能用在更复杂的寻路场景里。
