散列表

散列表的核心思想：通过散列函数将键转化为数组索引，实现快速查找和插入。
两步操作：
1. 用散列函数将键映射为数组索引。
2. 处理碰撞冲突（多个键映射到同一索引）。
权衡：时间与空间的平衡。
- 无内存限制：键直接作为索引，查找O(1)，但空间需求巨大。
- 无时间限制：顺序查找，空间少但时间O(N)。
- 散列表：在两者间取折中，可通过参数调整性能。
性能：基于概率论，均摊后查找和插入操作接近常数级别。

目标：
- 将任意键映射到[0, M-1]的整数。
- 易计算且均匀分布（每个索引被选中的概率相等）。
与键类型相关：
- 每种键类型需特定散列函数。
- Java提供默认hashCode()方法，返回32位整数。
典型实现：
- 正整数：除留余数法k % M，M为素数以确保均匀性。
- 浮点数：乘M并四舍五入，或转为二进制后除留余数。
- 字符串：Horner方法，将字符串视为R进制数，计算(R * hash + char) % M。
- 组合键：如Date类，混合多个整数域(day * R + month) * R + year % M。
Java约定：
- hashCode()与equals()一致。
- 自定义类型需重写两者，默认返回内存地址不适用。
转化为索引：
- (x.hashCode() & 0x7fffffff) % M：屏蔽符号位，取余M。
设计要求：
- 一致性：相等键散列值相等。
- 高效性：计算简单。
- 均匀性：键均匀分布。
- 需避免忽略键高位，确保每位参与计算。

原理：
- 用M个链表存储N个键值对，散列值相同的键放入同一链表。
- 查找：散列找到链表，顺序查找键。
实现：
- SeparateChainingHashST：数组st[]存SequentialSearchST对象。
- put()：计算散列值，插入对应链表。
- get()：计算散列值，查找对应链表。
性能：
- 命题K：链表长度在N/M的常数因子内（假设均匀散列）。
- 命题L：未命中查找和插入比较次数~N/M。
- 平均链表长度α=N/M，M大则链表短，查找快。
调整M：
- M过大浪费空间，过小链表长效率低。
- 可动态调整数组大小（如N/M>8时倍增）。
删除：找到链表，调用其delete()。
局限：不支持有序操作（如找最大/最小键）。

原理：
- 开放地址法，M>N，用数组空位解决碰撞。
- 碰撞时线性探测下一位置（索引+1），直到命中或空位。
实现：
- LinearProbingHashST：并行数组keys[]和vals[]。
- put()：探测至空位或已有键，插入或更新。
- get()：探测至命中或空位。
删除：
- 删除后需将右侧键重新插入，避免断链。
键簇：
- 连续占用位置形成簇，簇长影响探测次数。
- 长簇概率随插入增加，需控制使用率α=N/M。
性能（命题M）：
- 命中探测次数1+1/(2(1-α))，未命中1+1/(2(1-α)²)。
- α=1/2时，命中约1.5次，未命中约2.5次。
- α接近1时性能急剧下降。
调整大小：
- α≥1/2时倍增M，α≤1/8时减半M，确保α在1/8到1/2间。