散列(哈希)查找：定义、散列函数设计与冲突处理

散列（哈希）查找是一种基于哈希表的数据结构与算法，用于快速存储和检索数据。在散列查找中，通过一个特定的哈希函数，将键（key）映射到一个数组中的位置，从而实现对数据的存储和检索。

一、散列函数设计

散列函数的主要目的是将键均匀地分布到哈希表中的各个槽位上，以尽可能减少哈希冲突。一个好的散列函数应具有简单性、均匀性和一致性。以下是一些常见的散列函数设计方法：

1. 直接定址法：根据键值直接计算出在哈希表中的位置。例如，对于一个简单的哈希表，可以将键值乘以一个常数，然后取结果的整数部分作为哈希值。
2. 除法法：将键值除以一个质数，取结果的余数作为哈希值。这种方法简单易懂，但可能会在某些情况下导致哈希冲突较多。
3. 平方取中法：将键值的平方后取中间几位作为哈希值。这种方法可以减少哈希冲突，但计算量较大。
4. 折叠法：将键值分割成多个部分，然后将各部分叠加求和，取结果的某个位数作为哈希值。这种方法可以根据具体情况调整哈希函数，但需要谨慎处理不同部分之间的权重问题。

二、处理哈希冲突的方法

由于散列函数的特性，难免会出现哈希冲突的情况。当两个不同的键被映射到同一个槽位上时，就需要采取一些策略来处理冲突。以下是一些常见的处理哈希冲突的方法：

1. 链地址法：当发生哈希冲突时，将冲突的元素链在同一个槽位上，形成一个链表。查找时需要对链表进行遍历，直到找到目标元素或遍历完整个链表。这种方法的优点是简单易实现，但可能会影响查找效率。
2. 开放地址法：当发生哈希冲突时，按照某种规则（如探测法或再哈希法）在哈希表中寻找下一个可用的槽位。常见的开放地址法有：

a. 线性探测法：从发生冲突的槽位开始，按照一定步长（通常是1）向后探测，直到找到可用的槽位或探测完整个哈希表。
b. 二次探测法：类似于线性探测法，但步长是按照二次方的规律变化。这种方法可以更好地均匀分布元素，减少哈希冲突。
c. 再哈希法：当发生冲突时，使用另一个哈希函数重新计算槽位地址。这种方法需要设计多个哈希函数，增加了实现的复杂性。

1. 再哈希表法：当某个槽位上的链表过长时，可以将其分裂成两个或多个小链表，并重新分配槽位。这种方法可以动态调整哈希表的大小，提高查询效率。
2. 公共溢出区：将发生冲突的元素存储在一个公共的溢出区中，当访问某个槽位上的元素时，需要先判断该元素是否在溢出区中。如果元素在溢出区中，则需要从溢出区中将该元素移动回原位或重新分配槽位。这种方法可以保证元素的相对位置不变，但需要维护额外的溢出区数据结构。

以上是散列查找中常见的散列函数设计和处理哈希冲突的方法。在实际应用中，应根据具体情况选择合适的散列函数和冲突处理策略，以提高数据存储和检索的效率。