【数据结构-查找】散列表

1 线性探测法

1.1 查找成功时的 ASL

• 查找元素 47（散列函数：3）次数：1
• 查找元素 7（散列函数：11）次数：1
• 查找元素 29（散列函数：7）次数：2
• 查找元素 11（散列函数：0）次数：1
• 查找元素 9（散列函数：9）次数：1
• 查找元素 84（散列函数：7）次数：4
• 查找元素 54（散列函数：10）次数：2
• 查找元素 20（散列函数：9）次数：6
• 查找元素 30（散列函数：8）次数：7
• 查找元素 23（散列函数：1）次数：2
• ASL_成功 = 1/10 * (1+1+2+1+1+4+2+6+7+2)

1.2 查找失败时的 ASL

• 查找的散列函数值为 0 的元素时的次数：5
• 查找的散列函数值为 1 的元素时的次数：4
• 查找的散列函数值为 2 的元素时的次数：3
• 查找的散列函数值为 3 的元素时的次数：2
• 查找的散列函数值为 4 的元素时的次数：1
• 查找的散列函数值为 5 的元素时的次数：1
• 查找的散列函数值为 6 的元素时的次数：1
• 查找的散列函数值为 7 的元素时的次数：11
• 查找的散列函数值为 8 的元素时的次数：10
• 查找的散列函数值为 9 的元素时的次数：9
• 查找的散列函数值为 10 的元素时的次数：8
• ASL_失败 = 1/11 * (5+4+3+2+1+1+1+11+10+9+8)

1.3 散列表的装填因子 α

• 装填因子α = 表中记录数 / 散列表长度 = 10/12
• ASL 依赖于装填因子 α，而不直接依赖于表中记录数和散列表长度
• α 越大，发生冲突的可能性越大，反之发生冲突的可能性越小

2 拉链法