TikTok Python Dict：Key、顺序、冲突与查询复杂度

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 使用Python 3.7及以上字典插入顺序保证，具体内存布局不作为语言保证。
• 不假设所有key的hash/eq是常量或无副作用。

解题路线

1. dict是键到值的映射，key必须可哈希，且相等key应具有相同hash。value可为可变对象；存入并不自动复制，所有权仍由接口合同决定。
2. Python 3.7起插入顺序是语言保证，不等于按key排序。更新已有key值不移动位置，删除后重新插入会成为最后项。需要key排序应显式sorted。
3. hash冲突不意味着覆盖任意key；哈希用于定位候选，eq区分键是否同一映射身份。只有相等键会代表同一项；True与1相等且hash相同，会落在同一键。
4. 查询平均常量依赖良好哈希分布与实现，最坏冲突或昂贵自定义hash/eq不能保证O(1)。n次插入也包含扩容与实际键比较成本。
5. 复合检查再写不是天然原子操作：if key not in cache再加载写入可能有竞态。解释器实现的线程保护不能替代业务多步骤锁或原子数据库约束。
6. 测试需覆盖重复相等key、顺序更新/重插、缺失键政策和可变value共享。get默认None时无法区分存None与缺失，可用独立sentinel或in检查。

手动走一遍

d={a:1,b:2}更新a仍是a,b顺序，删a再插成为b,a。{True:yes,1:one}只有一项，因为键相等。None是合法value，因此get返回None不一定不存在。

规模与取舍

常见实现查写平均O(1)、迭代O(n)、内存O(n)加键值对象；最坏查询可线性且需计hash/eq成本。排序key另需O(n log n)比较。

易错点与追问

容易失分的边界

• 有序就是按key排序。
• hash相同便一定同key。
• if-then字典操作当作并发事务。

继续深挖

• 为什么可变key危险？
• 删除重插如何影响LRU实现？
• None与缺失怎样设计API？