Ⅰ Hash表处理冲突的方法
处理哈希表中的冲突是关键任务，当关键字映射到的哈希地址已被占用时，需要寻找一个"空"的位置。常见的解决冲突策略有开放寻址法、拉链法和建立公共溢出区。
开放寻址法分为几种变体：线性探查法，从初始哈希地址开始，逐个尝试直到找到空位置或表满。线性探查法有简单线性、二次探测和伪随机探测。线性探查要求装填因子α不大于0.5至0.9，以确保高效性。二次探查法虽然避免了线性探查的聚集现象，但可能错过整个空间。双重散列法使用两个散列函数，效果更佳。
拉链法则是通过链接冲突的哈希地址，形成单链表，散列表的长度m决定了单链表的长度。拉链法允许较高的装填因子，但一般保持在1以下。
建立公共溢出区方法是在哈希表之外设置一个额外的存储空间，用于存放冲突的记录。这种方法对哈希函数的值域要求明确，同时对装填因子没有严格限制。
性能分析显示，散列表的查找时间取决于冲突和哈希函数的质量。查找成功的平均查找长度优于顺序和二分查找，而查找不成功的长度则取决于冲突的数量。散列表的平均查找长度与装填因子α有关，可以通过选择合适的α来优化性能。对比其他查找方法，如顺序查找和二分查找，散列法不依赖关键字比较，查找时间期望为常数时间o(1)。
以h(k) = (3k) % 11和线性探测再散列为例，构造哈希表并计算等概率下查找不成功的平均查找长度，需要具体计算和分析，这里略去具体数值的计算过程。
hashing定义了一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。