第十二单元：哈希函数 · 键到索引的映射魔术

封神冰川的农场里,牦牛并不是被随手扔进格子里的——农民用一套神奇的算法,把每头牦牛的名字直接翻译成一个格子编号。只要你知道名字,套用同样的算法一算,就能瞬间知道它在哪个格子,再也不用挨个翻找。这套"从名字算出位置"的魔法,正是计算机科学里大名鼎鼎的哈希函数(hash function)。这一单元由两个关卡组成,你将掌握如何设计哈希函数、如何用 ord() 取字符编码、如何用取模把结果"塞"进有限的格子里,以及哈希背后"存取一致"的核心思想。

12.1.1 什么是哈希函数（What Is a Hash Function）

12.1.1.1 把任意键变成一个数字 Turn any key into a number

哈希函数是一种把输入(键,key)转换成固定范围整数(哈希值)的函数。在本单元里,键是牦牛或士兵的名字(字符串),哈希值则是一个可以当作数组下标用的数字。它的魔力在于:同一个名字,每次算出来的编号永远相同——于是"算一次就能定位",无需逐个查找。

12.1.2 哈希表与键值映射（Hash Tables and Key-Value Mapping）

12.1.2.1 哈希函数是哈希表的心脏 The hash function is the heart of a hash table

在计算机中,哈希表(hash table / 哈希映射)是一种把"键"映射到"值"的数据结构。它用哈希函数计算出一个索引,指向数组中该记录应该存放的位置。这样一来,存数据和查数据都能在接近常数时间内完成——无论表里有多少元素,定位一个键的代价几乎不变。这正是哈希表相比链表、数组"顺序查找"的巨大优势。

12.2.1 ord() 取 ASCII 码（Getting the ASCII Code）

12.2.1.1 每个字符背后都有一个数字 Every character has a number behind it

计算机里没有"字母",只有数字。每个字符都对应一个整数编码,这套编码表就是 ASCII。Python 的内置函数 ord() 能把一个字符转换成它的编码:比如 ord("A") 是 65,ord("B") 是 66,ord("a") 是 97。哈希函数正是靠 ord() 把"字符串键"变成"可计算的数字"的第一步。

# ord() 把单个字符转为它的 ASCII 编码
ord("A")   # → 65
ord("B")   # → 66
ord("Z")   # → 90
ord("a")   # → 97

12.2.2 遍历字符串取码（Iterating Over a String）

12.2.2.1 逐个字符累加编码 Add up the code of each character

要把整个名字变成一个数字,常见做法是遍历字符串的每个字符,用 ord() 取码后累加。可以用索引循环 for i in range(len(name)) 取出 name[i],也可以直接 for letter in name。这是"哈希魔术"关卡里求和法哈希的核心步骤。

# 遍历字符串,累加每个字符的 ASCII 码
total = 0
for i in range(len(name)):
    letter = name[i]
    total += ord(letter)   # 把这个字符的码加进总和

# 更简洁的写法:直接遍历字符
for letter in name:
    total += ord(letter)

12.3.1 首字母法（First-Letter Method）

12.3.1.1 只看第一个字母 Look only at the first letter

"散列的牦牛"关卡用了一个非常简单的哈希函数:取名字第一个字母的 ASCII 码,再减去 65(因为 "A" 的码是 65),这样 A 开头得 0、B 开头得 1……最后取模限制在格子数内。这个方案只在"每头牦牛首字母各不相同"时才可靠,但对当前关卡已经够用。

# "散列的牦牛":首字母哈希函数
def hashName(name):
    asciiCode = ord(name[0])   # 取首字母的 ASCII 码
    return (asciiCode - 65) % 12   # 减 65 归零, 再对 12(格子数)取模

12.3.2 求和法（Sum Method）

12.3.2.1 把所有字母的码加起来 Add up the codes of all letters

"哈希魔术"关卡用了更结实的方案:把名字里每个字符的 ASCII 码全部相加,得到一个大数,再取模归一化。相比只看首字母,求和法让名字的每一个字母都参与计算,不同名字更不容易撞到同一个编号,分布也更均匀。

# "哈希魔术":求和哈希函数(尚未取模)
def hashName(name):
    hash = 0
    for i in range(len(name)):
        letter = name[i]
        hash += ord(letter)   # 累加每个字符的码
    return hash   # ← 下一步还要对 totalCells 取模

12.4.1 用取模限制范围（Constrain the Range with %）

12.4.1.1 把大数"折"进格子里 Fold a big number into the slot range

字符编码相加常常得到很大的数(几百甚至上千),但格子只有有限个(如 12 个或 135 个)。取模运算 % 正是解决之道:hash % totalCells 会得到 0 到 totalCells - 1 之间的余数,恰好落在合法的索引范围内。这一步叫作归一化(normalize),是每个哈希函数不可或缺的收尾。

# "哈希魔术":用取模把哈希值压进 0~134
totalCells = 135
def hashName(name):
    hash = 0
    for letter in name:
        hash += ord(letter)
    hash = hash % totalCells   # 归一化到 0~134
    return hash

12.4.2 索引从 0 开始（Indices Start at Zero）

12.4.2.1 为什么模 N 得到 0 到 N-1 Why modulo N yields 0 to N-1

任何整数对 N 取模,结果一定在 0 到 N-1 之间——这正好对应一个长度为 N 的数组的所有合法下标。所以 135 个格子就模 135(得 0~134),12 个格子就模 12(得 0~11)。取模的数必须等于格子总数,这样才能既不越界、又能用满每一个格子。

12.5.1 用哈希定位（Locate by Hash）

12.5.1.1 用键算出地址 Compute an address from the key

要存或取某条信息,就用它的键(name)作为参数调用哈希函数,得到的数字就是它在内存(格子阵列)中的地址。存的时候(PUT)把数据放进那个格子;取的时候(GET)去那个格子拿数据。整个过程不需要遍历,一算即达。

# 用键调用哈希函数得到存储地址
key = "someName"
hero.say("它在第 " + hashFunction(key) + " 号格子")

12.5.2 一致性原则（Consistency Principle）

12.5.2.1 存和取必须用同一个哈希函数 Use the same hash function to store and to search

这是哈希表最关键的规则:存(PUT)和取(GET)必须使用完全相同的哈希函数。"哈希魔术"关卡里,你用士兵名字算出位置把他们放好(PUT),圣骑士再用同一个哈希函数算出位置去找他们(GET)。只要函数一致,同一个名字必然指向同一个格子——存进去的东西才找得回来。若两边算法不同,存取的地址就对不上,数据就"丢"了。

12.6.1 什么是碰撞（What Is a Collision）

12.6.1.1 不同键算出同一个索引 Different keys yielding the same index

哈希函数把大量可能的键压进有限的格子里,难免出现两个不同的键算出相同哈希值的情况——这就叫碰撞(collision)。比如首字母法里,两头都以 "B" 开头的牦牛会撞到同一格;求和法里,"abc" 和 "cba" 字母和相同也会相撞。碰撞是哈希表无法完全避免的固有现象,真实系统会用"链地址法""开放寻址"等技术来化解。不过在本单元的两关里,数据经过精心设计,不会发生碰撞,你可以先专注于哈希函数本身的设计。

这一节聚焦每一关的策略、思路与算法设计,只展示用于说明的关键片段,完整通关程序请你自己动手完成。

第 28 关 · 散列的牦牛

🐂 散列的牦牛 —— 用首字母哈希找到格子号

图2：散列的牦牛——牦牛按名字的哈希值分格存放;对清醒牦牛的名字套用哈希函数,算出格子号来召唤它们

策略:对每个清醒牦牛的名字算哈希、说出格子号

牦牛按名字的哈希值分格存放,你只能"按格子号"召唤牦牛,而且不能吵醒睡着的。农民会给你一份清醒牦牛的名字列表(yakList)。策略很清晰:遍历这份名字列表,对每个名字调用哈希函数算出格子号,再把号码说出来,即可精准召唤,不惊扰睡牦牛。

思路拆解:遍历名单 + 逐个哈希

先拿到农民的 yakNameList;哈希函数 hashName 取首字母 ord(name[0])、减 65、对 12 取模。然后用 for yakName in yakNameList 遍历,对每个名字 hero.say(hashName(yakName)) 说出结果。核心就是把"遍历列表"和"调用哈希函数"组合起来。

# 关键片段:哈希函数 + 遍历名单
def hashName(name):
    asciiCode = ord(name[0])
    return (asciiCode - 65) % 12

# 遍历清醒牦牛名单,逐个说出格子号
for yakName in yakNameList:
    hero.say(hashName(yakName))   # 说出号码 = 召唤该牦牛

只召唤清醒的：之所以用农民给的"清醒名单"而非所有牦牛,是因为对睡着牦牛的名字算哈希、召唤它会吵醒它导致失败。名单本身就是一层过滤——只对该处理的键做哈希,是这一关的巧妙之处。

首字母法的前提：这一关能用"只看首字母"是因为牦牛们首字母各不相同,不会碰撞。如果有两头牦牛都叫 B 开头,这个简单哈希就会把它们算到同一格——这正好引出下一关为什么要用"求和法"。

第 29 关 · 哈希魔术

✨ 哈希魔术 —— 求和哈希实现 PUT 与 GET

图3：哈希魔术——用士兵名字的字符编码之和(取模 135)计算位置;存(PUT)与取(GET)用同一哈希函数,才能找回魔法

策略:完成求和哈希函数,对每个士兵说出名字与哈希

只有 135 个格子,所以哈希值必须归一化到 0~134。策略分三步:① 遍历名字累加每个字符的 ASCII 码;② 用取模把和压进 0~134;③ 遍历所有士兵,说出"名字 + 空格 + 哈希值"。这样存(PUT)时定位、圣骑士取(GET)时用同一函数定位,才能对上号。

思路拆解一:补全求和 + 取模的哈希函数

默认代码里 hash 从 0 开始,循环累加 ord(letter),但缺了归一化。关键是在 return 前补上 hash = hash % totalCells,把可能上千的和折进合法索引范围。这是本关最核心的一行。

# 关键片段:求和 + 取模归一化
totalCells = 135
def hashName(name):
    hash = 0
    for i in range(len(name)):
        letter = name[i]
        hash += ord(letter)
    hash = hash % totalCells   # ← 关键:归一化到 0~134
    return hash

思路拆解二:遍历士兵,输出名字与哈希

用 findByType("soldier") 拿到所有士兵,遍历时对每个士兵 hero.say(soldier.id + " " + hashName(soldier.id))。注意名字和数字之间要用空格分隔——这是关卡的格式要求。用 soldier.id 作为键传入哈希函数,存取都以它为准。

# 关键片段:遍历士兵,说出"名字 空格 哈希"
soldiers = hero.findByType("soldier")
for soldier in soldiers:
    hero.say(soldier.id + " " + hashName(soldier.id))

别忘了取模，否则越界：本关最容易漏掉的就是 hash % totalCells。字符编码之和轻易超过 135,若不取模,得到的索引会远超格子范围,圣骑士就找不到魔法的位置。取模这一步是让哈希"落地"的关键。

PUT 与 GET 的默契：这一关的精髓在于"存取一致"——你用 hashName 摆放士兵(PUT),圣骑士也用同一个 hashName 寻找(GET)。只要函数不变,同名必同位。这正是哈希表能可靠工作的根本保证。

12.8.1 新手最容易踩的坑（Pitfalls for Beginners）

12.8.1.1 哈希函数的典型问题 Typical issues with hash functions

图4：忘记取模、ord 传整串、取模数与格子数不符、存取用了不同函数,是本单元最常见的失误