Python 数据结构
速查手册

每块存30位，支持无限精度。小整数 -5~256 预缓存单例，不重复分配内存。

x = 10 ** 100         # 任意精度，无溢出
abs(-5)               # 5
bin(10)              # '0b1010'
int("1010", 2)       # 10，二进制转换
divmod(17, 5)        # (3, 2)
pow(2, 10, 1000)    # 24，模幂运算

直接封装 C double，有空闲列表缓存已释放对象。精度与 C/Java double 完全一致。

import math
round(3.14159, 2)             # 3.14
math.isclose(0.1+0.2, 0.3)   # True ✅
0.1 + 0.2 == 0.3             # False ❌
float('inf')                  # 正无穷
math.isnan(float('nan'))     # True

按字符范围自动选最小编码，哈希值缓存（第二次O(1)），短字符串自动驻留（interning）。

s = "Hello, 世界"
s.upper() / s.lower()         # 大小写
s.strip() / s.split(",")      # 去空白/分割
s.startswith("He")            # True
s.find("世")                   # 返回索引
",".join(["a","b","c"])      # "a,b,c"
f"value={42:.2f}"              # f-string
s[1:4] / s[::-1]               # 切片/反转

存储 PyObject 指针，扩容策略约 n*9//8+6，均摊 O(1) append。

lst = [3, 1, 4, 1, 5]
lst.append(9)           # 末尾添加 O(1)均摊
lst.extend([2, 6])      # 批量添加
lst.insert(0, 0)        # 头部插入 O(n)!
lst.pop()               # 末尾删除 O(1)
lst.pop(0)              # 头部删除 O(n)!
lst.sort(key=lambda x:x, reverse=True)
[x**2 for x in lst if x>2] # 推导式

无 allocated 字段，比 list 省内存。小 tuple（≤20元素）有空闲列表缓存，创建极快。可哈希，可作为 dict key。

t = (1, 2, 3)
t = 1, 2, 3            # 省略括号
a, b, c = t           # 解包
a, *rest = t          # 星号解包，rest=[2,3]
t.count(1)            # 计数
t.index(2)            # 查找索引
t + (4, 5)            # 拼接返回新tuple
d = {(1,2): "val"}    # 可作dict key

稀疏 indices 数组 + 紧凑 entries 数组，负载因子 2/3 触发扩容，自动保持插入顺序，开放寻址解决冲突。

d = {"a": 1, "b": 2}
d["c"] = 3             # 添加/修改 O(1)
d.get("x", 0)         # 安全获取，默认0
d.pop("a")            # 删除并返回
d.update({"d": 4})   # 批量更新
d.keys() / d.values() / d.items()
"b" in d              # 成员检测 O(1)
{k:v for k,v in d.items() if v>1}
d1 | d2               # 合并 Python 3.9+

与 dict 结构相似但不存 value，负载因子 2/3 扩容。frozenset 不可变可哈希，可作 dict key。

s = {1, 2, 3}
s.add(4)              # O(1)
s.discard(99)         # 删除，不存在不报错
s1 | s2               # 并集
s1 & s2               # 交集
s1 - s2               # 差集
s1 ^ s2               # 对称差集
1 in s                # 成员检测 O(1)
frozenset(s)          # 不可变版本

每块64元素的双向链表，两端 O(1) 操作，比 list 头部操作快得多。maxlen 实现有界缓冲区。

from collections import deque
d = deque([1,2,3], maxlen=5)
d.appendleft(0)    # 左端添加 O(1)
d.popleft()        # 左端删除 O(1)
d.append(4)        # 右端添加 O(1)
d.pop()            # 右端删除 O(1)
d.rotate(2)        # 右旋2步

底层哈希表与 dict 完全相同，仅重写 __missing__ 方法，访问不存在的 key 时自动调用 default_factory。

from collections import defaultdict
d = defaultdict(int)    # 默认0
d = defaultdict(list)   # 默认[]
d["missing"] += 1       # 不报KeyError
# 分组经典用法
groups = defaultdict(list)
for k, v in pairs:
    groups[k].append(v)

dict 子类，missing 返回0但不写入。most_common() 内部用 heapq.nlargest，时间 O(n log k)。

from collections import Counter
c = Counter("aabbbc")
# Counter({'b':3,'a':2,'c':1})
c.most_common(2)    # [('b',3),('a',2)]
c["z"]              # 0，不报错
c.update("aaa")     # 增量更新
c1 + c2             # 合并（过滤<=0）
c1 & c2             # 取最小计数
list(c.elements())  # 展开为列表

在 dict 哈希表之外额外维护双向链表，每个 key 对应链表节点，支持 O(1) 的 move_to_end。Python 3.7+ 普通 dict 已有序但不支持此操作。

from collections import OrderedDict
od = OrderedDict()
od["a"] = 1
od.move_to_end("a")            # 移到末尾 O(1)
od.move_to_end("b", last=False) # 移到开头
od.popitem(last=True)          # 删除最后一个
# LRU Cache 核心实现基础

动态生成 tuple 子类代码（exec），属性访问通过 __slots__ + property 实现为下标访问，内存极省。

from collections import namedtuple
Point = namedtuple("Point", ["x","y"])
p = Point(1, 2)
p.x              # 1，属性访问
p[0]             # 1，下标访问
p._replace(x=10) # 返回新对象
# 推荐现代写法
from typing import NamedTuple
class Point(NamedTuple):
    x: int; y: int; z: int = 0

内部仅是 list 持有原 dict 引用，零复制，查找按顺序线性扫描。写操作只写入第一个 dict。

from collections import ChainMap
defaults = {"color":"red", "size":10}
overrides = {"color":"blue"}
cm = ChainMap(overrides, defaults)
cm["color"]      # "blue"（优先第一个）
cm["size"]       # 10（fallback）
cm.new_child()   # 添加最高优先级层
cm.parents       # 去掉第一层的视图

基于普通 list 实现的最小堆，满足 heap[k] <= heap[2*k+1]。所有操作维护堆不变量，不是独立类，直接操作 list。

import heapq

# 建堆：O(n)
h = [3, 1, 4, 1, 5]
heapq.heapify(h)         # [1,1,4,3,5] O(n)

# 入堆 / 出堆：O(log n)
heapq.heappush(h, 2)     # 推入 O(log n)
heapq.heappop(h)        # 弹出最小值 O(log n)
h[0]                     # 查看堆顶 O(1)

# 替换操作（更高效）
heapq.heapreplace(h, 9) # 弹出+推入 O(log n)
heapq.heappushpop(h, 0)# 推入后弹出 O(log n)

nlargest/nsmallest 内部用 heapq 实现，比全排序快（O(n log k) vs O(n log n)）。最大堆用负值技巧，自定义顺序用元组。

import heapq

# Top K 问题
heapq.nlargest(3, data)          # 最大3个 O(n log k)
heapq.nsmallest(3, data)         # 最小3个 O(n log k)
heapq.nlargest(3, data, key=abs) # 自定义key

# 最大堆：取负值
maxh = []
heapq.heappush(maxh, -5)         # 推入-5
-heapq.heappop(maxh)             # 取出5

# 自定义优先级（元组排序）
heapq.heappush(h, (1, "任务A"))   # (优先级, 数据)
heapq.heappush(h, (3, "任务B"))
pri, task = heapq.heappop(h)

# 合并多个有序迭代器
heapq.merge([1,3], [2,4])        # 懒惰合并 O(n log k)

针对已排序 list 的二分操作，时间 O(log n)，但插入仍需 O(n) 移位。bisect_left 和 bisect_right 的区别在于等值元素插到左侧还是右侧。

import bisect

a = [1, 3, 5, 7, 9]

# 查找插入位置 O(log n)
bisect.bisect_left(a, 5)    # 2 (左边界)
bisect.bisect_right(a, 5)   # 3 (右边界)
bisect.bisect(a, 5)          # 同 bisect_right

# 插入并保持有序 O(n)
bisect.insort_left(a, 4)    # 插入4，保持升序
bisect.insort(a, 6)         # 同 insort_right

# 支持 lo/hi 限定范围
bisect.bisect_left(a, 5, 0, 3) # 只搜索 a[0:3]

bisect 的真正价值在于将 O(n) 的线性搜索优化为 O(log n)，常用于有序数组的范围查询、排名计算和分段函数映射。

import bisect

a = [1, 3, 5, 7, 9]

# 精确查找（是否存在）
def find(a, x):
    i = bisect.bisect_left(a, x)
    return i < len(a) and a[i] == x

# 统计区间内元素数量
def count_range(a, lo, hi):
    return bisect.bisect_right(a, hi) - bisect.bisect_left(a, lo)

# 分段函数（成绩等级映射）
breakpoints = [60, 70, 80, 90]
grades      = ["F","D","C","B","A"]
def grade(score):
    return grades[bisect.bisect(breakpoints, score)]

# 查找小于等于x的最大元素（floor）
def floor_val(a, x):
    i = bisect.bisect_right(a, x)
    return a[i-1] if i else None

所有 itertools 函数返回惰性迭代器，不提前计算全部结果，内存友好。组合数学相关函数等价于数学定义但更高效。

from itertools import *

# 笛卡尔积
list(product("AB", 2**0, [0,1]))   # repeat参数
list(product([0,1], repeat=3))     # 二进制枚举

# 排列（有序，不重复抽取）
list(permutations("ABC"))          # 全排列 3!
list(permutations("ABC", 2))       # A(3,2)=6

# 组合（无序，不重复抽取）
list(combinations("ABCD", 2))     # C(4,2)=6

# 组合（允许重复）
list(combinations_with_replacement("AB", 2))
# [AA, AB, BB]

无限迭代器需配合 islice/takewhile 截断。groupby 要求输入已按 key 排序，否则不会合并不相邻的相同组。chain 零复制拼接多个迭代器。

from itertools import *

# 无限迭代器
count(10, 2)              # 10,12,14,... 步长2
cycle([1,2,3])           # 1,2,3,1,2,3,...
repeat(0, 5)             # 0,0,0,0,0

# 截取无限迭代器
list(islice(count(1), 5)) # [1,2,3,4,5]

# 分组（需先排序）
data = sorted([("A",1),("B",2),("A",3)], key=lambda x:x[0])
for k, g in groupby(data, key=lambda x:x[0]):
    print(k, list(g))

# 链式拼接（零复制）
list(chain([1,2],[3,4],[5]))  # [1,2,3,4,5]
list(chain.from_iterable([[1,2],[3]])) # 同上

# 累积
list(accumulate([1,2,3,4]))   # [1,3,6,10] 前缀和

lru_cache 内部用字典 + 双向链表实现 LRU，参数须可哈希。cache（3.9+）等价于 maxsize=None 的无界缓存。

from functools import lru_cache, cache, reduce, partial

# 记忆化缓存（DFS/DP利器）
@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

@cache                       # 无界版本，Python 3.9+
def dp(i, j): ...

fib.cache_info()             # hits, misses, maxsize
fib.cache_clear()            # 清空缓存

# 归约
reduce(lambda a,b: a*b, [1,2,3,4]) # 24

# 偏函数：固定参数
double = partial(pow, exp=2)
double(5)                    # 25

Python 标准库缺少平衡BST，sortedcontainers 用分块列表模拟，在竞赛环境（LeetCode/Codeforces）可用，性能接近 C++ std::set。

from sortedcontainers import SortedList, SortedDict

sl = SortedList([3,1,4,2])
sl.add(5)               # 自动保持有序 O(log n)
sl.discard(3)           # 删除 O(log n)
sl[0]                   # 最小值 O(1)
sl[-1]                  # 最大值 O(1)
sl.bisect_left(3)       # 二分查找位置
sl.irange(2, 4)         # 范围迭代 [2,3,4]
sl.count(3)             # 计数 O(log n)

sd = SortedDict({"b":2, "a":1})
sd.peekitem(0)          # 最小key的(k,v)
sd.peekitem(-1)         # 最大key的(k,v)

Python 中"一切皆对象"的代价：每个对象无论多小，都必须携带两个 8 字节指针。这是动态类型 + 引用计数 GC 的根本开销。

# PyLongObject (int) 完整布局
# ob_refcnt  8B  ← 引用计数，0时释放内存
# ob_type    8B  ← 指向 &PyLong_Type
# ob_size    4B  ← digit 个数（大整数）
# padding    4B  ← 内存对齐
# ob_digit   4B  ← 实际数值（30 bits/digit）
# 合计 = 28 bytes，但只存了 4B 有效数据

import sys
sys.getsizeof(0)       # 28
sys.getsizeof(2**30)    # 32  (2 digits)
sys.getsizeof(2**100)   # 52  (4 digits)

CPython 启动时预创建 -5 ~ 256 的所有整数对象，同范围整数赋值直接复用，不新建对象。字符串驻留对看起来像标识符的短字符串自动开启。

# 小整数缓存
a = 256; b = 256
a is b          # True！同一对象，节省内存

a = 257; b = 257
a is b          # False，各自新建 28 bytes

# 字符串驻留
s1 = "hello"; s2 = "hello"
s1 is s2        # True（纯字母字符串自动驻留）

s1 = "hello world"  # 有空格，不自动驻留
s2 = "hello world"
s1 is s2        # False（取决于实现，不可依赖）

# 强制驻留
import sys
s1 = sys.intern("hello world")
s2 = sys.intern("hello world")
s1 is s2        # True

碰撞不可避免（鸽巢原理），关键是碰撞后怎么处理。Python 选开放寻址：所有数据存在同一块连续内存，CPU cache 命中率高，对小型 dict（Python 最常见场景）性能更好。

开放寻址删除元素不能直接清空槽位，否则会截断探针链，导致后续查找失败。CPython 用 dummy 对象标记已删除槽。

# 场景：cat→slot1，dog→slot1碰撞→探针到slot3
# 删除 slot1 的 cat，如果直接清空：
# 查找 dog：hash→1，slot1为空 → 误判不存在！

# 正确做法：slot1 放 DUMMY（墓碑）
# 槽的三种状态：
#   empty  → 从未用过，查找时停止探针
#   dummy  → 已删除，查找时继续探针
#   active → 有效数据，比较 key
# 插入时：遇到 dummy 可复用（等同空槽）

两个函数都是标准左闭右开二分，唯一差别在比较条件：bisect_left 用 <，bisect_right 用 <=，决定碰到相等元素时是停在左边还是右边。

import bisect
arr = [1, 3, 3, 3, 5, 7]

bisect.bisect_left(arr, 3)    # → 1  (第一个3的位置)
bisect.bisect_right(arr, 3)   # → 4  (最后一个3之后)
bisect.bisect(arr, 3)         # → 4  (bisect = bisect_right)

# 手写等价（面试中可能要求）：
def bisect_left(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:   # 严格小于 → 左边不够
            lo = mid + 1
        else:
            hi = mid
    return lo

def bisect_right(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= target:  # 小于等于 → 继续往右
            lo = mid + 1
        else:
            hi = mid
    return lo

insort 的复杂度陷阱：bisect 部分 O(log n)，但 list.insert 移位是 O(n)，整体 O(n)。需要真正 O(log n) 插入请用 SortedList。

import bisect

# 1. 存在性查找
def contains(arr, target):
    i = bisect.bisect_left(arr, target)
    return i < len(arr) and arr[i] == target

# 2. floor（最大的 ≤ target，金融：不超过某价格的最大档位）
def floor_val(arr, target):
    i = bisect.bisect_right(arr, target) - 1
    return arr[i] if i >= 0 else None

# 3. ceiling（最小的 ≥ target）
def ceil_val(arr, target):
    i = bisect.bisect_left(arr, target)
    return arr[i] if i < len(arr) else None

# 4. 区间计数（[lo, hi] 内有多少元素，O(log n)）
def count_range(arr, lo, hi):
    return bisect.bisect_right(arr, hi) - bisect.bisect_left(arr, lo)

# 5. 时间序列定位（tick数据按时间戳二分）
import bisect
timestamps = [930100, 930200, 930305, 930410]  # HHMMSS
idx = bisect.bisect_left(timestamps, 930300)
# idx=2，即 930305 是第一个 >= 09:03:00 的tick

# 6. insort 陷阱：O(n) 不是 O(log n)！
bisect.insort(arr, 6)   # bisect O(logn) + list.insert O(n) = O(n)
# 需要真 O(log n) 插入 → 用 SortedList