哈希冲突：哈希表为什么会冲突？如何解决？

哈希表通过哈希函数将键映射到数组位置，但若不同键映射到同一位置则产生哈希冲突，核心原因是键数量远超数组容量或哈希函数不均。解决冲突的核心是让冲突键“各占位置”，常见方法有： 1. **链地址法（拉链法）**：最常用，每个数组位置为链表，冲突键依次挂在对应链表后，如键5、1、9冲突时，链表为5→1→9。查找时遍历链表，实现简单且空间利用率高。 2. **开放定址法**：冲突时从后续位置找空位，包括线性探测（步长1）、二次探测（步长平方）、双重哈希（多函数映射），但易聚集或实现复杂。 3. **公共溢出区**：主数组存无冲突键，冲突键放入溢出区，查找需主区+溢出区遍历，空间分配难。 解决冲突需依场景选择，链地址法因高效通用被广泛采用，理解冲突及解决方法可优化哈希表性能。