哈希表链地址法和开放定址法的时间复杂度

哈希表的存储通常使用两种解决冲突的主要方法：链地址法和开放定址法。

1. 链地址法（Separate Chaining）：当哈希函数将不同的键映射到同一个槽位时，每个槽位会是一个链表。查找、插入和删除操作需要先通过哈希函数找到对应槽位，然后遍历这个链表。时间复杂度通常是O(1)（平均情况），但在最坏的情况下，如果所有元素都哈希到同一个槽位，链表长度将达到n，此时查找、插入和删除的时间复杂度变为O(n)。

2. 开放定址法（Open Addressing）：当发生冲突时，寻找下一个空的槽位继续存储，而不是创建新的链表。常见的开放地址法策略有线性探测（Linear Probing）、二次探测（Quadratic Probing）和双散列（Double Hashing）。查找操作需要不断探测直到找到目标值或者发现冲突的解决方案。理想情况下，平均查找时间也是O(1)，但在最坏情况下，可能出现“聚集”现象，使得查找变成线性的，即O(n)。

总结一下：
- 查找：链地址法平均O(1)，最坏O(n)；开放定址法平均O(1)，最坏也可能是O(n)。
- 插入和删除：链地址法都需要遍历链表，所以时间复杂度都是O(n)。