哈希冲突：哈希表为什么会冲突？如何解决？
哈希表通过哈希函数将键映射到数组位置，但若不同键映射到同一位置则产生哈希冲突，核心原因是键数量远超数组容量或哈希函数不均。解决冲突的核心是让冲突键“各占位置”，常见方法有： 1. **链地址法（拉链法）**：最常用，每个数组位置为链表，冲突键依次挂在对应链表后，如键5、1、9冲突时，链表为5→1→9。查找时遍历链表，实现简单且空间利用率高。 2. **开放定址法**：冲突时从后续位置找空位，包括线性探测（步长1）、二次探测（步长平方）、双重哈希（多函数映射），但易聚集或实现复杂。 3. **公共溢出区**：主数组存无冲突键，冲突键放入溢出区，查找需主区+溢出区遍历，空间分配难。 解决冲突需依场景选择，链地址法因高效通用被广泛采用，理解冲突及解决方法可优化哈希表性能。
阅读全文哈希函数：哈希函数如何生成哈希值？初学者必知
哈希函数是将任意长度输入转为固定长度哈希值的“翻译器”，哈希值即数据的“身份证号”。其核心特点：固定长度（如MD5为32位十六进制字符）、单向不可逆（无法由哈希值反推原数据）、近似唯一（碰撞概率极低）、雪崩效应（输入微小变化致哈希值巨变）。生成过程分三步：输入预处理为二进制，分段数学运算，合并结果。与加密函数不同，哈希单向无需密钥，加密可逆需密钥。应用广泛：文件校验（比对哈希值防篡改）、密码存储（存哈希值保安全）、数据索引及分布式系统数据分布。哈希如数据指纹，关键特性使其在安全与校验中不可或缺。
阅读全文