hash表

1.散列表

散列技术是在记录的存储位置和它的关键词之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）

• 散列技术最适合的求解问题是查找与给定值相等的记录
• 相同关键字可以

2.散列函数

• 散列函数的计算时间不应该超过其他查找技术与关键词比较时间

• 散列地址分布均匀

• 直接定址法 f(key)=a*key+b
  简单均匀，也不会产生冲突，适合查找表较小且连续的情况

• 除留余数法 f(key)=key mod p (p<=m)

• 处理散列冲突的方法

  • 线性探测法
    一旦发生了冲突，就去寻找下一个空的散列地址，只要散列足够大，空的散列地址总能找到，并将记录存入
  • 二次探测法
    双向寻找可能的空位置，同事增加平方运算，不让关键词都聚集在某一块区域
    还可以使用伪随机数，如果设置随机种子相同，每次得到的数列是相同的

• 再散列函数法
  每当发生散列地址冲突时，就换一个散列函数计算，总有一个可以把冲突解决掉