哈希冲突：哈希表为什么会冲突？如何解决？
哈希表通过哈希函数将键映射到数组位置，但若不同键映射到同一位置则产生哈希冲突，核心原因是键数量远超数组容量或哈希函数不均。解决冲突的核心是让冲突键“各占位置”，常见方法有： 1. **链地址法（拉链法）**：最常用，每个数组位置为链表，冲突键依次挂在对应链表后，如键5、1、9冲突时，链表为5→1→9。查找时遍历链表，实现简单且空间利用率高。 2. **开放定址法**：冲突时从后续位置找空位，包括线性探测（步长1）、二次探测（步长平方）、双重哈希（多函数映射），但易聚集或实现复杂。 3. **公共溢出区**：主数组存无冲突键，冲突键放入溢出区，查找需主区+溢出区遍历，空间分配难。 解决冲突需依场景选择，链地址法因高效通用被广泛采用，理解冲突及解决方法可优化哈希表性能。
阅读全文哈希表冲突怎么办？简单看懂数据结构的哈希解决方法
哈希表通过哈希函数映射键到数组槽位，不同键映射同一槽位即哈希冲突。解决核心是为冲突元素找新位置，主要方法如下： 1. **链地址法（拉链法）**：每个槽位存链表，冲突元素挂在链表上。例如键1、6、11哈希到同一槽位，其链表为[1,6,11]。优点：实现简单，适合动态数据；缺点：需额外空间存链表，查找最坏O(n)。 2. **开放寻址法**：冲突时找空槽位，分线性探测（i+1循环）和二次探测（i+1²等）。如键6哈希到槽位1冲突，线性探测到2；键11到3。优点：空间利用率高；缺点：线性探测易聚集，二次探测需更大数组。 其他方法：再哈希法（多哈希函数）、公共溢出区（基本表+溢出表），适合冲突少场景。选择依场景：链地址法（如Java HashMap）适合动态大量数据；开放寻址法适合固定数组、冲突少场景。
阅读全文哈希表怎么存数据？哈希函数让查找变简单
文章用找书类比引出问题：顺序查找数据（如数组）效率低，哈希表是高效存储工具。哈希表核心是哈希函数，将数据映射到“桶”（数组位置），实现快速存取。哈希函数把数据转为哈希值（桶编号），如学号取后两位得哈希值。存储时，先算哈希值定位桶，若多数据哈希值相同（冲突），用链表法（桶内挂链表）或开放寻址法（找下一个空桶）解决。查找时，直接算哈希值定位桶，再在桶内查找，无需遍历全部数据，速度极快。哈希表应用广泛（如通讯录、缓存），核心是用哈希函数将查找从“翻遍”转为“直达”。
阅读全文