散列,就是通过某种精心设计的算法将一段可能很长的数据转化为较短的信息串(通常为固定长度),广泛应用于网页传输中的协议,软件完整性检查,计算机安全领域等。
散列表是通过特定的哈希算法将一个大的集合映射出一个小的集合,从而的到一个更方便检索的关键码。
哈希算法有很多种形式例如数字分析法,中平法,折叠法,这里我采用的是除余法。
基本思路:
取出列表中的每个元素除以待存贮的列表的长度取余数 ,将余数作为关键码,由于是将一个大集合映射成为一个小集合所以必然出现冲突的情况,解决冲突我采用开地址的方法,当发生冲突的时候,将索引加1,直到找到一个空位置时,存入数据。
开始代码:
1. 准备数据和存储表,为了实现字典,和方便获取索引值(如果我的存储列表为空,那么我是无法获取索引值的),我通过循环向列表里填充了-1
2. 用除余法定义散列函数,求出数值所对应的关键码,当出现冲突时,用变量a 记录,每次发生冲突a+1,用于求出平均查找长度,同时index 也要加1,用于算出正确的关键码,这时出现了一个情况:如果出现了一种较坏的情况index加到了超出列表的索引范围。就应该将索引值设为0,从头开始存入数据
3. 根据数据在列表中检索找到数据(算法和插入类似),返回数据的关键码,没找到返回flase
4.主函数和输出
整体代码