哈希表：快速查找的存储结构

哈希表是一种数据结构，通过哈希函数将元素的关键码映射到一个固定的位置，理论上能实现 O(1) 的查找速度。其核心是解决哈希冲突，常见的解决方法有闭散列和开散列。

哈希冲突与哈希函数

哈希冲突是指不同关键字通过同一哈希函数计算出相同位置。解决冲突的方法包括设计合理的哈希函数，如直接定址法、除留余数法等，以及处理冲突的策略，如线性探测和二次探测。

哈希函数示例

直接定址法：取关键字的线性函数作为地址

除留余数法：取关键字与哈希表长度取模，常用且广泛

其他方法：平方取中法、折叠法、随机数法等，针对不同场景

冲突解决策略

闭散列（开放定址法）：线性探测和二次探测，如 Java 限制荷载因子

开散列（链地址法）：将相同哈希地址的元素链接到链表，如 HashMap 中的数组+链表+红黑树

哈希表的实现

闭散列：每个位置存储数据和状态，用数组（如 vector）实现

开散列：每个位置存储链表头结点，增容时遍历原表插入新表

优化与比较

开散列虽然看似增加存储开销，但通过减少空闲空间的需求，实际节省存储。选择哪种方法取决于具体应用场景和性能需求。