散列，hash

.散列像用于两组数组的比对，将两个数组的数据散列开，比对查找。数字大的时候，时间复杂度会很高，因此用空间换时间，有三种方法（应用场合）：

1.用于判断M数组中的数在N数组中是否出现过：

定义 bool 型 数组 hashTable[Maxn]; //Maxn取数据上限；

（记住）使用前要先初始化，表示初始状态下所有数都没有出现过；

示例：const int Maxn=100010;

           bool hashTable[Maxn]={false};

hashTable[x]=true;//x有出现过；

hashTable[x]=false;//x没有出现过；

自我解读：hashTable数组像一个标记，把读过的每一个数做上记号，等到再次出现时会显示之前的属性（即有没有出现过）；

例题：判断M中的数字有没有在N中出现过；

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
   const int Maxn=100;//假设所有数据不超过100；
4.  
   bool hashTable[Maxn]={false};//表示初始状态下所有数字都没有出现过；
5.  
   int main()
6.  
   {
7.  
   int i,m,n,x; // m,n谁的数据多无所谓
8.  
   cout<<"请输入n,m内部元素个数：\n";
9.  
   cin>>n>>m;
10.  
    cout<<"请输入n中元素：\n";
11.  
    for(i=0;i<n;i )
12.  
    {
13.  
    cin>>x;
14.  
    hashTable[x]=true;//标记N中已有的数据x；(读入的时候进行预处理)
15.  
    }
16.  
    cout<<"请输入m中元素：\n";
17.  
    for(i=0;i<m;i )
18.  
    {
19.  
    cin>>x;
20.  
    if(hashTable[x]==false)//注意判断的方法！
21.  
    cout<<"NO!\n";
22.  
    else cout<<"YES!\n";
23.  
    }
24.  
    return 0;
25.  
    }

时间复杂度为O(N M);因为只是将两个数组中的元素都扫描了一遍（边输入便记录，吼吼） 

 2.判断M中的每个数在N中出现的次数

定义int 型hashTable[Maxn]; //Maxn取数据上限；

以上两种方法的共性：将输入的元素作为数组下标，来统计这个数的性质；

将查询操作的时间复杂度降到O(1)，空间换时间常用法！！

例题：判断M中的每个数在N中出现的次数

1.  
   #include <iostream>
2.  
   using namespace std;
3.  
   const int Maxn=100;//假设所有数据不超过100；
4.  
   int hashTable[Maxn]={0};//表示初始状态下所有数字都没有出现过；
5.  
   int main()
6.  
   {
7.  
   int i,m,n,x; // m,n谁的数据多无所谓
8.  
   cout<<"请输入n,m内部元素个数：\n";
9.  
   cin>>n>>m;
10.  
    cout<<"请输入n中元素：\n";
11.  
    for(i=0;i<n;i )
12.  
    {
13.  
    cin>>x;
14.  
    hashTable[x] ;//标记N中已有的数据x；
15.  
    }
16.  
    cout<<"请输入m中元素：\n";
17.  
    for(i=0;i<m;i )
18.  
    {
19.  
    cin>>x;
20.  
    cout<<"出现次数：";
21.  
    cout<<hashTable[x]<<"\n";
22.  
    }
23.  
    return 0;
24.  
    }

（注意输入m的时候，按回车就会传递数据，可以输一个判断一次，也可以整体输，整体判断） 

3.散列（hash）:将元素通过一个函数转换为整数，并且用这个元素尽可能唯一的代表这个元素

(1）除留余数法：H（key）=key%mod  ;

将余数作为hash值。若mod为素数，H(key)能尽可能覆盖[0,mod)的每一个数，所以一般取表长为素数，令mod等于表长（！）

若H(key)相同，即有“冲突”，有三种解决方法：

1)线性探查法：即下标为H(key)的位置已被占用，检查H(key) 1的位置，直至有位置，若超过表长还没有位置，就回到表的首位继续循环。

2）平方探查法

3）链地址法

将h(key)相同的key连接成一条链表，于是冲突时，可以通过遍历单链表寻找所有的key.

这篇好文章是转载于：学新通技术网