手写哈希表核心是散列函数、底层数组和链地址法；需用质数长度数组，散列函数须处理负hash，链表头插并查重，负载因子超0.7时扩容rehash，key必须可哈希且不可变。
哈希表自己写，核心就三件事：散列函数、数组底层数组、链地址法处理冲突
Python 里 dict 是 C 实现的哈希表，自己手写不是为了替代它，而是搞懂 __hash__ 怎么用、为什么 list 不能当 key、冲突时链表怎么接——这些在调试或实现自定义容器时真会卡住你。
用数组 + 链表是最直白的实现路径，但别一上来就写完整类。先聚焦「插入」和「查找」两个动作，其他都是围绕它们补的逻辑。
- 数组长度建议用质数（比如 7、11、101），避免某些散列值周期性撞在同一索引
- 散列函数别直接用
hash(obj) % size：Python 的hash()对字符串返回值可能为负，得先转成非负整数：hash(obj) & 0xffffffff - 链表节点存
(key, value)元组，不是只存value——否则无法判断 key 是否已存在
冲突发生时，链表头插还是尾插？选头插，但得小心重复 key
头插快（O(1)），但每次 setitem 前必须遍历当前链表检查 key 是否已存在，否则会留下重复 key 的脏数据。尾插省了查重，但要维护尾指针或每次遍历找尾，实际更慢。
所以标准做法是头插 + 查重。查重过程顺便也完成了“更新已有 key”的逻辑——这正是 Python dict[key] = val 的行为。
立即学习“Python免费学习笔记（深入）”；
- 查重必须比对
key is other_key或key == other_key，不能只靠 hash 值相等（不同 key 可能 hash 相同） - 如果 key 是自定义类，记得实现
__eq__和__hash__，且两者逻辑一致：a == b时必须有hash(a) == hash(b) - 不处理重复 key 的典型现象：
my_hash_table['x'] = 1; my_hash_table['x'] = 2后查出来还是 1
扩容时机和 rehash 的坑：负载因子 > 0.7 就该扩，但扩完必须全量 rehash
数组满了才扩容太晚，性能会断崖下跌。Python dict 内部用负载因子（元素数 / 数组长度）控制，超过 0.666… 就触发扩容。自己写可以宽松点，设成 0.7 就够用。
扩容不是简单把数组变长，而是新建更大数组（通常 ×2 或 ×2+1），再把所有旧键值对重新算 hash、插入新数组——这个过程叫 rehash。漏掉 rehash，数据就丢了。
- 扩容后数组长度必须仍是质数，别直接
size *= 2，要用预定义质数表或写个简单质数检测 - rehash 时旧链表里的每个节点都要走一遍插入逻辑（含查重），不是 memcpy 过去
- 如果扩容期间还在并发读写，会出现数据错乱——手写哈希表默认不考虑线程安全，这点容易被忽略
Python 中哪些类型不能当 key？不是报错才叫问题
list、dict、set 不能当 key，因为它们可变，__hash__ 返回 NotImplemented，一塞进去就抛 TypeError: unhashable type。但这只是表象。
真正麻烦的是看似不可变、实则可能被改的类型，比如自定义类没锁死属性、或者用了 __slots__ 却忘了禁写。一旦 key 被修改，它的 hash 值可能变，后续就再也找不到这个键了——没有报错，只有静默失败。
- 检查 key 是否可哈希：用
hash(key)试试，不抛异常才算过关 - 用
tuple当 key 没问题，但里面嵌套了list（如(1, [2])）就不行 - 调试时发现 key 找不到，优先打印
hash(key)和对应桶里的所有节点的hash值，看是否错位
