数据结构----哈希_hash 随机数

哈希（hash）:

目的：可以在第一时间确定这个值到底在不在这个数组

哈希冲突：不同数据的关键字通过哈希函数得到一个相同的地址，这时就发生冲突，这种冲突叫哈希冲突。

       总结：根据设定好的哈希函数和处理发生哈希冲突的解决方法，将一组数据的关键字用哈希函数可以映射到一组连续且有限的地址集（区间）内，可以将映射到地址集上的像记录在表中，这个表就是哈希表，这个映射的过程一般叫哈希表或者散列，这种映射关系叫哈希函数或散列函数。

       哈希是一种储存防=方式，也是你一种查找方式。

       算法中只要用到这个哈希思想，就可以叫做哈希算法（hash）。

哈希函数的构造方法：六种方法可以揉起来使用

1、直接定址法     y = ax + b     a、b都是常量

2、数字分析法

3、折叠法

4、除留余数法： 最常用的构造散列函数方法，对于散列表长为m的散列函数公式为 ：

                                                       f(key) = key mod p(p<=m)

mod 是取余数的意思。

5、随机数法

 6、平方取中法

 如何处理哈希冲突：

1、开放地址法： 

线性探测法：

二次探测法：

 

 随机探测法：

 2、再散列函数法

3、链地址法

4、公共区溢出法

 基本上可以通过hash确定地址，但是溢出表一般是鞍顺序储存，所以溢出表只能是从前向后遍历