哈希表

哈希表(好不容易搞懂了)

知识讲解

如果存储和使用线性表（1,75,324,43,1353,90,46），那么，只要定义一个一维数组和a[7],将表中元素按先后顺序存储在a[i]中即可。但是，这样的存储结构会给“查找算法”带来O(n)的时间开销，尤其是n很大时，效率比较差。当然，也可以采用“二分查找”提高效率。反之，为了用O(1)的时间实现查找，可以分析这个线性表的元素类型和范围，定义一个一维数组a[1353],使得a[key]=key，即线性表的key这个元素存储在a[key]中。这样一来，查找的时间效率高了，空间上的开销却大了，尤其是数据范围分布很广时。为了使空间开销减小，可以对这种方法进行优化，设计一个函数h(key)=key mod 13,然后把key存储在a[h(hey)]中。这样一来，只要定义一个一维数组a[12]就足够了。这种线性表的这种结构称之为哈希表(Hash Table)

哈希表，又称散列表。是利用关键字与地址的直接映射关系产生的列表。他的最大优势在于，一个关键字对应一个存储位置（理想情况下），而我们直接就可以由key值找到其在散列表中的位置，大大缩减了我们查找的时间。

哈希表的构造方法

哈希表构造原则：1.计算简单，复杂算法将会影响查找上的优势 2.散列地址分布均匀，这样我们不需要过多的解决散列表冲突问题，提高效率。

构造具体方法：

由于是比较简单的哈希表，因此哈希函数我选择了简单的除留余数法f(key)=key mod p(p<=m)。
处理冲突的时候，我采用了开放定址法f(key) = (f(key)+di) mod m(di=1,2,3,4...m-1)

例题

题目描述

好吧，题目是这样的：给出一串数以及一个数字 C，要求计算出所有 A-B=C 的数对的个数。（不同位置的数字一样的数对算不同的数对）

输入输出格式

输入格式：

第一行包括

第二行有

输出格式：

输出一行，表示该串数中包含的所有满足

输入输出样例

输入样例#1：

4 1
1 1 2 3

输出样例#1：

3


例题代码

 1 #include <iostream>
 2     #include <map>
 3     using namespace std;
 4     typedef long long LL;
 5     LL a[200001];
 6     map<LL,LL> m;
 7     int main() {
 8         int n;
 9         LL c;
10         LL ans=0;
11         cin >> n >> c;
12         for(int i=1;i<=n;i++) {
13             cin >> a[i];
14             m[a[i]]++;
15             a[i]-=c;    
16         } 
17         for(int i=1;i<=n;i++) ans+=m[a[i]];
18         cout << ans << endl;
19         return 0;
20 }