2哈希元素的存取 ................................ ................................ ................................ ...........…

哈希表通过哈希函数将键映射到存储位置，实现常数时间复杂度的元素存取。哈希函数应当均匀分布以减少冲突。常见冲突解决方法有： 1. 开放地址法：当冲突发生时，在哈希表中探测下一个空闲位置。探测方式包括线性探测、二次探测和双重哈希。线性探测简单但可能产生聚集；二次探测可缓解聚集；双重哈希采用两个哈希函数，分布更均匀。 2. 链地址法：每个哈希桶对应一个链表（或红黑树），冲突元素挂在同一链上。查找时先计算哈希值，再遍历链表。Java HashMap中当链表长度超过阈值时会转为红黑树以优化性能。 3. 再哈希法：发生冲突时使用另一个哈希函数重新计算位置。 4. 建立公共溢出区：将冲突元素存入额外空间。 存取操作包括： - 插入：计算哈希值，根据冲突解决策略找到空位或插入链表；若负载因子过高则需动态扩容。 - 查找：计算哈希值，按相同策略定位并比较键。 - 删除：在开放地址法中不能直接删除，否则影响后续查找，常用惰性删除标记；链地址法直接链表删除。 哈希表性能受哈希函数质量、负载因子和冲突解决方法影响。理想情况下查找、插入、删除均接近O(1)，但最坏情况可能退化到O(n)。